arXiv preprint ·
Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
- Published
- Source
- arXiv preprint, posted before peer review
- DOI
- 10.1016/j.orl.2024.107217
- Original
- Read it at arXiv
- Topics
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) 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Envy-free Allocations with Individual Payments
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.