An improved approximation algorithm for the minimum common integer partition problem

Given a collection of multisets () of positive integers, a multiset is a for them if is an integer partition of every multiset . The (-MCIP) problem is defined as to find a CIP for with the minimum cardinality. We present a -approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio designed by Chen et al. in 2006. We then extend it to obtain an absolute 0.6-approximation algorithm for -MCIP when is even (when is odd, the approximation ratio is ).