An improved approximation algorithm for the minimum common integer partition problem

Given a collection of multisets { X 1, X 2, …, X k } ( k ≥ 2 ) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X i, 1 ≤ i ≤ k. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for { X 1, X 2, …, X k } with the minimum cardinality. We present a 6 5 -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio 5 4 designed by Chen et al. 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. 6 k + 0. 4 ).

Authors

• Guohui Lin
• Weitian Tong

Keywords

• Approximation algorithm
• Integer partition
• Weighted set packing
• Amortized analysis