Greedy Local Improvement and Weighted Set Packing Approximation

Barun Chandra*, Magnús M. Halldórsson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

81 Citations (Scopus)

Abstract

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k - 1. However, neither paradigm can yield approximations that improve on this. We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.

Original languageEnglish
Pages (from-to)223-240
Number of pages18
JournalJournal of Algorithms
Volume39
Issue number2
DOIs
Publication statusPublished - May 2001

Other keywords

  • Approximation algorithms
  • Greedy algorithms
  • Local search
  • Set packing
  • Weighted independent set

Fingerprint

Dive into the research topics of 'Greedy Local Improvement and Weighted Set Packing Approximation'. Together they form a unique fingerprint.

Cite this