Two for one swap heuristic gives new approximation for polymatroid independent sets
Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
Data Structures and Algorithms
Summary
This paper studies a way to find large independent sets in a special mathematical structure called a k-polymatroid, which has applications in optimization. Finding the biggest independent set is easy for k=2 but hard for k>=3. The authors analyze a simple method that swaps two elements for one in the current set repeatedly. They show this method achieves an approximation ratio that is slightly weaker but easier to understand than previous methods.
What this means in practice
- •For optimization software developers: Improve approximation algorithms for hard combinatorial problems modeled by k-polymatroids using the two-for-one swap heuristic analysis.
- •For network design engineers: Explore better heuristics for selecting large independent sets in network resource allocation problems that map to k-polymatroids.
A theory result. No direct application yet.
Authors
Adrian Calinescu, Gruia Calinescu
Abstract
Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We call a subset S of N independent if f(S) equals the sum of f(e) over the elements e of S and f(e) > 0 for all e in S. Finding a maximum-size independent set in a 2-polymatroid has been studied and polynomial-time algorithms are known for linear polymatroids. For k >= 3, the problem is NP-hard, and an approximation algorithm with ratio approaching 2/k is known and is obtained by swapping as long as possible a "large" subset from the current solution by a set with one more element. Here we give a simple analysis of the more particular two-for-one repeated swapping heuristic, obtaining a (weaker) 2/(k+1)-approximation.