Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Better Approximations for the Minimum Common Integer Partition Problem
verfasst von : David P. Woodruff
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
k
-Minimum Common Integer Partition Problem, abbreviated
k
-MCIP, we are given
k
multisets
X
1
, ...,
X
k
of positive integers, and the goal is to find an integer multiset
T
of minimal size for which for each
i
, we can partition each of the integers in
X
i
so that the disjoint union (multiset union) of their partitions equals
T
. This problem has many applications to computational molecular biology, including ortholog assignment and fingerprint assembly.
We prove better approximation ratios for
k
-MCIP by looking at what we call the
redundancy
of
X
1
, ...,
X
k
, which is a quantity capturing the frequency of integers across the different
X
i
. Namely, we show .614
k
-approximability, improving upon the previous best known (
k
– 1/3)-approximability for this problem. A key feature of our algorithm is that it can be implemented in almost
linear time
.