Browsing by Author "Chang, Huilan"

Now showing 1 - 9 of 9

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.
Identification and Classification Problems on Pooling Designs for Inhibitor Models
(2010-07-01)
Chang, Huilan
;
Chen, Hong-Bin
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
Pooling designs are common tools to efficiently distinguish positive clones from negative clones in clone library screening. In some applications, there is a third type of clones called "inhibitors'' whose effect is in a sense to obscure the positive clones in pools. Various inhibitor models have been proposed in the literature. We address the inhibitor problems of designing efficient nonadaptive procedures for both identification and classification problems, and improve previous results in three aspects: (1) The algorithm that is used to identify the positive clones works on a more general inhibitor model and has a polynomial-time decoding procedure that recovers the set of positives from the knowledge of the outcomes. (2) The algorithm that is used to classify all clones works in one-stage, i.e., all tests are arranged in advance without knowing the outcomes of other tests, along with a polynomial-time decoding procedure. (3) We extend our results to pooling designs on complexes where the property to be screened is defined on subsets of biological objects, instead of on individual ones.
Learning a hidden graph
(2014-12-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
We study the problem of learning a hidden graph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. We provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with n vertices and m edges in m log n + 10m + 3n edge-detecting queries.
Learning a hidden uniform hypergraph
(2018-01-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
Motivated by applications in genome sequencing, Grebinski andKucherov (Discret Appl Math 88: 147-165, 1998) studied the graph learning problem which is to identify a hidden graph drawn from a given class of graphs with vertex set {1, 2,..., n} by edge-detecting queries. Each query tells whether a set of vertices induces any edge of the hidden graph or not. For the class of all hypergraphs whose edges have size at most r, Chodoriwsky and Moura (Theor Comput Sci 592: 1-8, 2015) provided an adaptive algorithm that learns the class in O(m(r) log n) queries if the hidden graph has m edges. In this paper, we provide an adaptive algorithm that learns the class of all r-uniform hypergraphs in mr log n + (6e)(r)m(r+1/2) queries if the hidden graph has m edges.
Limit theorems for patterns in phylogenetic trees
(2010-04-01)
Chang, Huilan
;
Fuchs, Michael
;
應用數學系
;
Department of Applied Mathematics
Studying the shape of phylogenetic trees under different random models is an important issue in evolutionary biology. In this paper, we propose a general framework for deriving detailed statistical results for patterns in phylogenetic trees under the Yule-Harding model and the uniform model, two of the most fundamental random models considered in phylogenetics. Our framework will unify several recent studies which were mainly concerned with the mean value and the variance. Moreover, refined statistical results such as central limit theorems, Berry-Esseen bounds, local limit theorems, etc., are obtainable with our approach as well. A key contribution of the current study is that our results are applicable to the whole range of possible sizes of the pattern.
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.
Reconstruction of hidden graphs and threshold group testing
(2011-08-01)
Chang, Huilan
;
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Shi, Chie-Huai
;
應用數學系
Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form "Does a set of elements contain a positive one?". A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form "Whether a set of vertices induces an edge". Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg n,(1+o(1))(nlg n),2n and 2n queries were proposed, respectively. In this paper we improve them to (1 + 0(1))(nlgn), (1+0(1)) (nlgn/2), n + 2lgn and n+lg n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds l and u, with l
The decycling number of outerplanar graphs
(2013-05-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Lien, Min-Yun
;
應用數學系
;
Department of Applied Mathematics
For a graph G, let tau(G) be the decycling number of G and c(G) be the number of vertex-disjoint cycles of G. It has been proved that c(G)a parts per thousand currency sign tau(G)a parts per thousand currency sign2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if tau(G)=c(G) and upper-extremal if tau(G)=2c(G). In this paper, we provide a necessary and sufficient condition for an outerplanar graph being upper-extremal. On the other hand, we find a class of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all , then G is lower-extremal.
Threshold Group Testing on Inhibitor Model
(2013-06-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
In classical group testing, one is given a population N and an unknown subset D subset of N of positive items, and the goal is to determine D by testing subsets of N. Threshold group testing is a generalization of classical group testing, where the outcome of a group test is determined by the number of positive items in the test. In group testing on inhibitor model, inhibitors are the third type of item that dictate the test outcome to be negative regardless of how many positives are in the test. The threshold group testing on k-inhibitor model is a natural combination of threshold group testing and inhibitor model. In this article, we provide nonadaptive algorithms to conquer the threshold group testing on k-inhibitor model where error-tolerance is considered. Furthermore, we provide a two-stage algorithm to identify all inhibitors and find a g-approximate set.