Approximating the k-Set Packing problem by local improvements

Martin Fürer, Huiwen Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Citations (SciVal)

Abstract

We study algorithms based on local improvements for the k-Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver [14] has been improved by Sviridenko and Ward [15] from to k/2 + ∈ to k+2/3, and by Cygan [7] to k+1/3 + ∈ for any ∈ > 0. In this paper, we achieve the approximation ratio k+1/3 + ∈ for the k-Set Packing problem using a simple polynomial-time algorithm based on the method by Sviridenko and Ward [15]. With the same approximation guarantee, our algorithm runs in time singly exponential in 1/∈2, while the running time of Cygan's algorithm [7] is doubly exponential in 1/∈. On the other hand, we construct an instance with locality gap k+1/3 for any algorithm using local improvements of size O(n1/5), where is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.

Original languageEnglish (US)
Title of host publicationCombinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers
PublisherSpringer Verlag
Pages408-420
Number of pages13
ISBN (Print)9783319091730
DOIs
StatePublished - 2014
Event3rd International Symposium on Combinatorial Optimization, ISCO 2014 - Lisbon, Portugal
Duration: Mar 5 2014Mar 7 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8596 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Symposium on Combinatorial Optimization, ISCO 2014
Country/TerritoryPortugal
CityLisbon
Period3/5/143/7/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Approximating the k-Set Packing problem by local improvements'. Together they form a unique fingerprint.

Cite this