On Local Search for Weighted k-Set Packing
- 1 August 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 23 (3) , 640-648
- https://doi.org/10.1287/moor.23.3.640
Abstract
Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k − 1 + 1/t. As a consequence, for any given r < 1/(k − 1) we can compute in polynomial time a solution whose weight is at least r times the optimal.Keywords
This publication has 8 references indexed in Scilit:
- On syntactic versus computational views of approximabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximation of k-set cover by semi-local optimizationPublished by Association for Computing Machinery (ACM) ,1997
- Approximating k-set cover and complementary graph coloringPublished by Springer Nature ,1996
- Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)Published by Springer Nature ,1995
- One-Half Approximation Algorithms for the k-Partition ProblemOperations Research, 1992
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing ProblemsSIAM Journal on Discrete Mathematics, 1989
- An extension of matching theoryJournal of Combinatorial Theory, Series B, 1986
- Packing subgraphs in a graphOperations Research Letters, 1982