TY - JOUR

T1 - An improved approximation algorithm for the minimum common integer partition problem

AU - Lin, Guohui

AU - Tong, Weitian

N1 - Publisher Copyright:
© 2021 Elsevier Inc.

PY - 2021/12

Y1 - 2021/12

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 [Formula presented]-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio [Formula presented] 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).

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 [Formula presented]-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio [Formula presented] 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).

KW - Amortized analysis

KW - Approximation algorithm

KW - Integer partition

KW - Weighted set packing

UR - http://www.scopus.com/inward/record.url?scp=85110557140&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2021.104784

DO - 10.1016/j.ic.2021.104784

M3 - Article

AN - SCOPUS:85110557140

SN - 0890-5401

VL - 281

JO - Information and Computation

JF - Information and Computation

M1 - 104784

ER -