TY - CHAP
T1 - An improved approximation algorithm for the minimum common integer partition problem
AU - Tong, Weitian
AU - Lin, Guohui
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - Given a collection of multisets {X1,X2,..., Xk} (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset Xi, 1 ≤ i ≤ k. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for {X1,X2,..., Xk} with the minimum cardinality. We present a 6/5 -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of ratio 5/4 designed in 2006. We then extend it to obtain an absolute 0.6k-approximation algorithm for k-MCIP when k is even (when k is odd, the approximation ratio is 0.6k + 0.4).
AB - Given a collection of multisets {X1,X2,..., Xk} (k ≥ 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset Xi, 1 ≤ i ≤ k. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for {X1,X2,..., Xk} with the minimum cardinality. We present a 6/5 -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of ratio 5/4 designed in 2006. We then extend it to obtain an absolute 0.6k-approximation algorithm for k-MCIP when k is even (when k is odd, the approximation ratio is 0.6k + 0.4).
UR - http://www.scopus.com/inward/record.url?scp=84921466252&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13075-0_28
DO - 10.1007/978-3-319-13075-0_28
M3 - Chapter
AN - SCOPUS:84921466252
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 353
EP - 364
BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
A2 - Ahn, Hee-Kap
A2 - Shin, Chan-Su
PB - Springer Verlag
ER -