A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem

Stefan Haller, Bogdan Savchynskyy

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 relaxatio…