Papers › A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem
A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem
Stefan Haller, Bogdan Savchynskyy
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We propose a scalable approximate algorithm for the NP-hard maximum-weight independent set problem, based on dual coordinate descent applied to a smoothed clique-cover LP relaxation. Our method, a variant of the Bregman/Sinkhorn algorithm, employs entropy smoothing with a novel duality-gap-based smoothing scheduling strategy that empirically outperforms standard feasibility scheduling for the relaxed problem. Our new projection to the primal feasible set enables accurate duality gap estimation. Combined with a basic primal heuristic leveraging reduced costs, our approach yields high-quality integer solutions. On real-world datasets, it efficiently finds high-quality approximate solutions for graphs with up to 882,000 nodes and 344 million edges within seconds.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections