The Experts below are selected from a list of 249 Experts worldwide ranked by ideXlab platform
Tao Jiang - One of the best experts on this subject based on the ideXlab platform.
-
On the minimum common Integer Partition problem
ACM Transactions on Algorithms, 2008Co-Authors: Xin Chen, Lan Liu, Zheng Liu, Tao JiangAbstract:We introduce a new combinatorial optimization problem in this article, called the minimum common Integer Partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A Partition of a positive Integer n is a multiset of positive Integers that add up to exactly n, and an Integer Partition of a multiset S of Integers is defined as the multiset union of Partitions of Integers in S. Given a sequence of multisets S1, S2, …, Sk of Integers, where k ≥ 2, we say that a multiset is a common Integer Partition if it is an Integer Partition of every multiset Si, 1 ≤ i ≤ k. The MCIP problem is thus defined as to find a common Integer Partition of S1, S2, …, Sk with the minimum cardinality, denoted as MCIP(S1, S2, …, Sk). It is easy to see that the MCIP problem is NP-hard, since it generalizes the well-known subset sum problem. We can in fact show that it is APX-hard. We will also present a 5/4-approximation algorithm for the MCIP problem when k e 2, and a 3k(k−1)/3k−2-approximation algorithm for k ≥ 3.
-
a network flow approach to the minimum common Integer Partition problem
Theoretical Computer Science, 2006Co-Authors: Wenbo Zhao, Peng Zhang, Tao JiangAbstract:In the k-Minimum Common Integer Partition Problem, abbreviated as k-MCIE we are given k multisets X1,...,Xk of positive Integers, the goal is to find an Integer multiset T of the minimum size such that for every i, we can Partition each of the Integers in Xi so that the disjoint (multiset) union of their Partitions equals T. This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any k ≥ 2. In this article, we improve the approximation ratio for k-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625k-approximation algorithm, improving upon the previously best known 0.6139k-approximation algorithm for this problem.
-
on the minimum common Integer Partition problem
Lecture Notes in Computer Science, 2006Co-Authors: Xin Chen, Lan Liu, Zheng Liu, Tao JiangAbstract:We introduce a new combinatorial optimization problem in this paper, called the Minimum Common Integer Partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A Partition of a positive Integer n is a multiset of positive Integers that add up to exactly n, and an Integer Partition of a multiset S of Integers is defined as the multiset union of Partitions of Integers in S. Given a sequence of multisets S 1 ,..., S k of Integers, where k ≥ 2, we say that a multiset is a common Integer Partition if it is an Integer Partition of every multiset Si, 1 ≤ i ≤ k. The MCIP problem is thus defined as to find a common Integer Partition of S 1 ,..., S k with the minimum cardinality. It is easy to see that the MCIP problem is NP-hard since it generalizes the well-known Set Partition problem. We can in fact show that it is APX-hard. We will also present a 5/4-approximation algorithm for the MCIP problem when k = 2, and a 3k(3k-1)/3k-2 -approximation algorithm for k ≥ 3.
-
A network flow approach to the Minimum Common Integer Partition Problem
Theoretical Computer Science, 2006Co-Authors: Wenbo Zhao, Peng Zhang, Tao JiangAbstract:AbstractIn the k-Minimum Common Integer Partition Problem, abbreviated as k-MCIP, we are given k multisets X1,…,Xk of positive Integers, the goal is to find an Integer multiset T of the minimum size such that for every i, we can Partition each of the Integers in Xi so that the disjoint (multiset) union of their Partitions equals T. This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any k⩾2. In this article, we improve the approximation ratio for k-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625k-approximation algorithm, improving upon the previously best known 0.6139k-approximation algorithm for this problem
Qilong Feng - One of the best experts on this subject based on the ideXlab platform.
-
fixed parameter tractability for minimum tree cut paste distance and minimum common Integer Partition
Theoretical Computer Science, 2020Co-Authors: Jie You, Jianxin Wang, Feng Shi, Qilong FengAbstract:Abstract Computational biology is mainly concerned with discovering an object from a given set of observations that are supposed to be good approximations of the real object. Two important steps here are to define a way to measure the distance between different objects and to calculate the distance between two given objects. The main problem is then to find an object that has the minimum total distance to the given observations. We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to transform a tree to another tree. The minimum common Integer Partition problem asks for a minimum-cardinality Integer Partition of a number that refines two given Integer Partitions of the same number. We give parameterized algorithms for both problems.
-
parameterized algorithms for minimum tree cut paste distance and minimum common Integer Partition
International Workshop on Frontiers in Algorithmics, 2018Co-Authors: Jie You, Jianxin Wang, Qilong FengAbstract:We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to apply to transform a tree to another tree. The minimum common Integer Partition problem asks for a minimum-cardinality Integer Partition of a number that refines two given Integer Partitions of the same number. We give parameterized algorithms for both problems.
Jie You - One of the best experts on this subject based on the ideXlab platform.
-
fixed parameter tractability for minimum tree cut paste distance and minimum common Integer Partition
Theoretical Computer Science, 2020Co-Authors: Jie You, Jianxin Wang, Feng Shi, Qilong FengAbstract:Abstract Computational biology is mainly concerned with discovering an object from a given set of observations that are supposed to be good approximations of the real object. Two important steps here are to define a way to measure the distance between different objects and to calculate the distance between two given objects. The main problem is then to find an object that has the minimum total distance to the given observations. We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to transform a tree to another tree. The minimum common Integer Partition problem asks for a minimum-cardinality Integer Partition of a number that refines two given Integer Partitions of the same number. We give parameterized algorithms for both problems.
-
parameterized algorithms for minimum tree cut paste distance and minimum common Integer Partition
International Workshop on Frontiers in Algorithmics, 2018Co-Authors: Jie You, Jianxin Wang, Qilong FengAbstract:We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to apply to transform a tree to another tree. The minimum common Integer Partition problem asks for a minimum-cardinality Integer Partition of a number that refines two given Integer Partitions of the same number. We give parameterized algorithms for both problems.
Yuri V. Yakubovich - One of the best experts on this subject based on the ideXlab platform.
-
Limit Shape of Minimal Difference Partitions and Fractional Statistics
'Springer Science and Business Media LLC', 2020Co-Authors: Leonid V. Bogachev, Yuri V. YakubovichAbstract:The class of minimal difference PartitionsMDP(q) (with gap q) is defined by the condition that successive parts in an Integer Partition differ from one another by at least q≥0. In a recent series of papers by A. Comtet and collaborators, the MDP(q) ensemble with uniform measure was interpreted as a combinatorial model for quantum systems with fractional statistics, that is, interpolating between the classical Bose–Einstein (q=0) and Fermi–Dirac (q=1) cases. This was done by formally allowing values q∈(0,1) using an analytic continuation of the limit shape of the corresponding Young diagrams calculated for Integer q. To justify this “replica-trick”, we introduce a more general model based on a variable MDP-type condition encoded by an Integer sequence q=(qi), whereby the (limiting) gap q is naturally interpreted as the Cesàro mean of q. In this model, we find the family of limit shapes parameterized by q∈[0,∞) confirming the earlier answer, and also obtain the asymptotics of the number of parts
-
Limit Shape of Minimal Difference Partitions and Fractional Statistics
Communications in Mathematical Physics, 2019Co-Authors: Leonid V. Bogachev, Yuri V. YakubovichAbstract:The class of minimal difference Partitions $$\text {MDP}(q)$$ MDP ( q ) (with gap q ) is defined by the condition that successive parts in an Integer Partition differ from one another by at least $$q\ge 0$$ q ≥ 0 . In a recent series of papers by A. Comtet and collaborators, the $$\text {MDP}(q)$$ MDP ( q ) ensemble with uniform measure was interpreted as a combinatorial model for quantum systems with fractional statistics , that is, interpolating between the classical Bose–Einstein ( $$q=0$$ q = 0 ) and Fermi–Dirac ( $$q=1$$ q = 1 ) cases. This was done by formally allowing values $$q\in (0,1)$$ q ∈ ( 0 , 1 ) using an analytic continuation of the limit shape of the corresponding Young diagrams calculated for Integer q . To justify this “replica-trick”, we introduce a more general model based on a variable MDP-type condition encoded by an Integer sequence $${\mathfrak {q}}=(q_i)$$ q = ( q i ) , whereby the (limiting) gap q is naturally interpreted as the Cesàro mean of $${\mathfrak {q}}$$ q . In this model, we find the family of limit shapes parameterized by $$q\in [0,\infty )$$ q ∈ [ 0 , ∞ ) confirming the earlier answer, and also obtain the asymptotics of the number of parts.
Jan Vondrák - One of the best experts on this subject based on the ideXlab platform.
-
Wide Partitions, Latin tableaux, and Rota's basis conjecture
Advances in Applied Mathematics, 2003Co-Authors: Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan VondrákAbstract:AbstractSay that μ is a “subPartition” of an Integer Partition λ if the multiset of parts of μ is a submultiset of the parts of λ, and define an Integer Partition λ to be “wide” if for every subPartition μ of λ, μ⩾μ′ in dominance order (where μ′ denotes the conjugate of μ). Then Brian Taylor and the first author have conjectured that an Integer Partition λ is wide if and only if there exists a tableau of shape λ such that (1) for all i, the entries in the ith row of the tableau are precisely the Integers from 1 to λi inclusive, and (2) for all j, the entries in the jth column of the tableau are pairwise distinct. This conjecture was originally motivated by Rota's basis conjecture and, if true, yields a new class of Integer multiflow problems that satisfy max-flow min-cut and integrality. Wide Partitions also yield a class of graphs that satisfy “delta-conjugacy” (in the sense of Greene and Kleitman), and the above conjecture implies that these graphs furthermore have a completely saturated stable set Partition. We present several partial results, but the conjecture remains very much open
-
Wide Partitions, Latin tableaux, and Rota's basis conjecture
arXiv: Combinatorics, 2002Co-Authors: Timothy Y. Chow, C. Kenneth Fan, Michel X. Goemans, Jan VondrákAbstract:Say that mu is a ``subPartition'' of an Integer Partition lambda if the multiset of parts of mu is a submultiset of the parts of lambda, and define an Integer Partition lambda to be ``wide'' if for every subPartition mu of lambda, mu >= mu' in dominance order (where mu' denotes the conjugate or transpose of mu). Then Brian Taylor and the first author have conjectured that an Integer Partition lambda is wide if and only if there exists a tableau of shape lambda such that (1) for all i, the entries in the ith row of the tableau are precisely the Integers from 1 to lambda_i inclusive, and (2) for all j, the entries in the jth column of the tableau are pairwise distinct. This conjecture was originally motivated by Rota's basis conjecture and, if true, yields a new class of Integer multiflow problems that satisfy max-flow min-cut and integrality. Wide Partitions also yield a class of graphs that satisfy ``delta-conjugacy'' (in the sense of Greene and Kleitman), and the above conjecture implies that these graphs furthermore have a completely saturated stable set Partition. We present several partial results, but the conjecture remains very much open.