  We propose a scalable approximate algorithm for the NP-hard maximum-weight
independent set problem. The core of our algorithm is a dual coordinate descent
applied to a smoothed LP relaxation of the problem. This technique is referred
to as Bregman method or Sinkhorn algorithm in the literature. Our algorithm
addresses a family of clique cover LP relaxations, where the constraints are
determined by the set of cliques covering the underlying graph. The objective
function of the relaxation is smoothed with an entropy term.
  An important question determining efficiency of our algorithm is the control
of the smoothing level over the course of optimization. While several dedicated
techniques have been considered in the literature to this end, we propose a new
one based on estimation of the relaxed duality gap. To make this estimation
possible, we developed a new projection method to the feasible set of the
considered LP relaxation. We experimentally show that our technique notably
outperforms the standard one based on feasibility estimation.
  Additionally to solving the relaxed dual, we utilize a simple and very
efficient primal heuristic to obtain feasible integer solutions of the initial
non-relaxed problem. Our heuristic is a combination of the greedy generation
and optimal recombination applied to the reduced costs computed by the dual
optimization.
  Our experimental validation considers two datasets based on real-life
applications, where our method shows competitive results being able to find
high quality approximate solutions within 10 seconds for graphs with hundreds
of thousands of nodes and dozens of millions of edges.
