@inbook{a8759ef9a13a4f4db940892904ec8583,
title = "An improved approximation algorithm for the minimum common integer partition problem",
abstract = "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).",
author = "Weitian Tong and Guohui Lin",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",
year = "2014",
doi = "10.1007/978-3-319-13075-0\_28",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "353--364",
editor = "Hee-Kap Ahn and Chan-Su Shin",
booktitle = "Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings",
address = "Germany",
}