Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid

Let f: 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). A k-polymatroid satisfies that f(e) <= k for all e is an element of N. We call S subset of N independent if f(S)=Sigma(e is an element of S)f(e) and f(e) > 0 for all e is an element of S. Such a set was also called a matching. 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 a ((2/k)-epsilon)-approximation is known and is obtained by swapping as long as possible a subset of up to (1/epsilon)(logk-1(2k+1)) elements 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 tight (weaker) (2/(k+1))-approximation.