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 [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).
Original language | English |
---|---|
Article number | 104784 |
Journal | Information and Computation |
Volume | 281 |
DOIs | |
State | Published - Dec 2021 |
Scopus Subject Areas
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
Keywords
- Amortized analysis
- Approximation algorithm
- Integer partition
- Weighted set packing