Browsing by Author "Hwang, Frank K."

Now showing 1 - 13 of 13

A competitive algorithm in searching for many edges in a hypergraph
(2007-02-15)
Chen, Ting
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
We give a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Damaschke did the d = 1 case for 2-graphs, Triesch extended the d = 1 case to r-graphs, and Johann did the general d case for 2-graphs. So ours is the first attempt to solve the searching for defective edges problem in its full generality. Further, all the above three papers assumed d known. We give a competitive algorithm where d is unknown. (c) 2006 Elsevier B.V. All rights reserved.
A new approach to solve open-partition problems
(2012-01-01)
Chang, Huilan
;
Hwang, Frank K.
;
Rothblum, Uriel G.
;
應用數學系
;
Department of Applied Mathematics
A partition problem in one-dimensional space is to seek a partition of a set of numbers that maximizes a given objective function. In some partition problems, the partition size, i.e., the number of nonempty parts in a partition, is fixed; while in others, the size can vary arbitrarily. We call the former the size-partition problem and the latter the open-partition problem. In general, it is much harder to solve open problems since the objective functions depend on size. In this paper, we propose a new approach by allowing empty parts and transform the open problem into a size problem allowing empty parts, called a relaxed-size problem. While the sortability theory has been established in the literature as a powerful tool to attack size partition problems, we develop the sortability theory for relaxed-size problems as a medium to solve open problems.
A polytope approach to the optimal assembly problem
(2006-07-01)
Hwang, Frank K.
;
Rothblum, Uriel G.
;
應用數學系
;
Department of Applied Mathematics
The problem of assembling components into series modules to maximize the system reliability has been intensively studied in the literature. Invariably, the methods employed exploit special properties of the reliability function through standard analytical optimization techniques. We propose a geometric approach by exploiting the assembly polytope - a polytope generated by the potential assembly configurations. The new approach yields simpler proofs of known results, as well as new results about systems where the number of components in a module is not fixed, but subject to lower and upper bounds.
A survey on nonadaptive group testing algorithms through the angle of decoding
(2008-01-01)
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
Group testing, sometimes called pooling design, has been applied to a variety of problems such as blood testing, multiple access communication, coding theory, among others. Recently, screening experiments in molecular biology has become the most important application. In this paper, we review several models in this application by focusing on decoding, namely, giving a comparative study of how the problem is solved in each of these models.
An upper bound of the number of tests in pooling designs for the error-tolerant complex model
(2008-06-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
Recently pooling designs have been used in screening experiments in molecular biology. In some applications, the property to be screened is defined on subsets of items, instead of on individual items. Such a model is usually referred to as the complex model. In this paper we give an upper bound of the number of tests required in a pooling design for the complex model (with given design parameters) where experimental errors are allowed.
Are there more almost separable partitions than separable partitions?
(2014-04-01)
Chang, Fei-Huang
;
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39-51, 1999; Barnes et al. in Math. Program. 54:69-86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285-289, 1967; Hwang et al. in SIAM J. Optim. 10:70-81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423-433, 2011a). In this paper, we prove that for da parts per thousand currency sign2 or pa parts per thousand currency sign2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.
Equivalence of permutation polytopes corresponding to strictly supermodular functions
(2008-06-28)
Hwang, Frank K.
;
Lee, J. S.
;
Rothblum, Uriel G.
;
應用數學系
;
Department of Applied Mathematics
This paper demonstrates a strong equivalence of all permutation polytopes corresponding to strictly supermodular functions. (C) 2007 Elsevier B.V. All rights reserved.
Exploring the missing link among d-separable, d-separable and d-disjunct matrices
(2007-03-15)
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
d-Disjunct matrices, (d) over bar -separable matrices and d-separable matrices are well studied in various problems including group testing, coding, extremal set theory and, recently, DNA sequencing. The implications from the first two matrices to the last one are well documented. This paper gives an implication of the other direction for the first time. (c) 2006 Elsevier B.X. All rights reserved.
On noninterruptive rearrangeable networks
(2006-10-01)
Hwang, Frank K.
;
Lin, Wen-Dar
;
Lioubimov, Vadim
;
應用數學系
;
Department of Applied Mathematics
In this paper,. we study a new class of nonblocking networks called noninterruptive rearrangeable (NIR) networks, which are rearrangeable under the additional condition that existing connections are not interrupted while their paths being possibly rerouted to accommodate a new request. We give a complete characterization of NIR Clos networks built of switching elements of various nonblocking properties. In particular, we propose a novel class of NIR Clos networks that leads to recursive constructions of various cost-efficient multistage NIR networks. Finally, we present examples of such constructions and compare them with the best previously known results.
Pooling designs for clone library screening in the inhibitor complex model
(2011-08-01)
Chang, Fei-huang
;
Chang, Huilan
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
In this paper we introduce inhibitors into the complex model and we give a lower bound and an upper bound of tests in a nonadaptive pooling design for some inhibitor complex model. We propose a very efficient pooling design for the general inhibitor complex model and extend it to the error-tolerant case.
Sphere-separable partitions of multi-parameter elements
(2008-03-15)
Golanya, Boaz
;
Hwang, Frank K.
;
Rothbluma, Uriel G.
;
應用數學系
;
Department of Applied Mathematics
We show the optimality of sphere-separable partitions for problems where n vectors in d-dimensional space are to be partitioned into p categories to minimize a cost function which is dependent in the sum of the vectors in each category; the sum of the squares of their Euclidean norms; and the number of elements in each category. We further show that the number of these partitions is polynomial in n. These results broaden the class of partition problems for which an optimal solution is guaranteed within a prescribed set whose size is polynormially bounded in n. Applications of the results are demonstrated through examples. (C) 2007 Elsevier B.V. All rights reserved.
Strictly nonblocking f-cast Log(d)(N, m, p) networks
(2007-05-01)
Hwang, Frank K.
;
Wang, Yang
;
Tan, Jinzhi
;
應用數學系
;
Department of Applied Mathematics
Necessary and sufficient conditions for Log(d) (N, m, p) network to be point-to-point strictly nonblocking are known. Recently, Kabacinski and Danilewicz obtained necessary and sufficient conditions for the Loge (N, 0, p) network to be broadcast strictly nonblocking. In this paper, we give necessary and sufficient conditions for Log(d)(N, m, p) to be f-cast strictly nonblocking for every f, thus covering the point-to-point case (f = 1) and the broadcast case (f = N) as special cases.
The mean-partition problem
(2006-09-01)
Chang, Fei-Hwang
;
Hwang, Frank K.
;
Rothblum, Uriel G.
;
應用數學系
;
Department of Applied Mathematics
In mean-partition problems the goal is to partition a finite set of elements, each associated with a d-vector, into p disjoint parts so as to optimize an objective, which depends on the averages of the vectors that are assigned to each of the parts. Each partition is then associated with a d x p matrix whose columns are the corresponding averages and a useful approach in studying the problem is to explore the mean-partition polytope, defined as the convex hull of the set of matrices associated with feasible partitions.