An improved approximation algorithm for the minimum common integer partition problem

Given a collection of multisets {X-1, X-2, . . . , 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 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.6k + 0.4). (C) 2021 Elsevier Inc. All rights reserved.