Theory of Computing
-------------------
Title     : On a Generalization of Iterated and Randomized Rounding
Authors   : Nikhil Bansal
Volume    : 20
Number    : 6
Pages     : 1-23
URL       : https://theoryofcomputing.org/articles/v020a006

Abstract
--------

We give a general method for rounding linear programs, that combines
the commonly used iterated rounding and randomized rounding
techniques. In particular, we show that whenever iterated rounding can
be applied to a problem with some slack, there is a randomized
procedure that returns an integral solution that satisfies the
guarantees of iterated rounding and also has concentration properties.
We use this to give new results for several classical problems such as
rounding column-sparse LPs, makespan minimization on unrelated
machines and degree-bounded spanning trees.


------------------

An extended abstract of this paper appeared in the Proceedings
of the 51st Annual ACM Symposium on Theory of Computing (STOC'19).