An improved approximation algorithm for the minimum common integer partition problem

Guohui Lin, Weitian Tong

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number104784
JournalInformation and Computation
Volume281
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'An improved approximation algorithm for the minimum common integer partition problem'. Together they form a unique fingerprint.

Cite this