20. Passing the Limits of Pure Local Search for Weighted k-Set Packing
Invited abstract in session WE-2: Combinatorial Optimization I, stream Discrete Optimization.
Wednesday, 14:45 - 16:15Room: C 103
Authors (first author is the speaker)
| 1. | Meike Neuwohner
|
| Department of Mathematics, London School of Economics and Political Science |
Abstract
Given a collection S of sets, each of cardinality at most k, and equipped with positive weights, the weighted k-Set Packing problem asks for a disjoint subcollection of S of maximum total weight. The case k = 2 is equivalent to weighted matching and can thus be solved in polynomial time.
For k >= 3, already the unweighted k-Set Packing problem, the special case where all weights are equal to 1, is NP-hard.
The technique that has proven most successful in designing approximation algorithms for both the unweighted and the weighted k-Set Packing problem is local search. For the unweighted problem, the state-of-the-art is a polynomial-time (k+1)/3+epsilon-approximation by Fürer and Yu. For general weights, we recently obtained a polynomial-time (k+epsilon_k)/2-approximation, where epsilon_k converges to 0 as k approaches infinity. We further proved that for general weights, one cannot achieve a better guarantee than k/2 by only considering local improvements of logarithmically bounded size.
In this talk, we show how to breach the k/2 barrier by employing a black box algorithm for the unweighted k-Set Packing problem to generate local improvements of super-logarithmic size. In doing so, we obtain a polynomial-time 0.4986*k+0.5194-approximation algorithm for weighted k-Set Packing. Our techniques further allow us to establish a general connection between the approximation guarantees achievable for unit and general weights.
Keywords
- Analysis and engineering of optimization algorithms
Status: accepted
Back to the list of papers