On a generalization of iterated and randomized rounding

Bansal, Nikhil

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 satisﬁes the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems such as rounding column-sparse LPs, makespan minimization on unrelated machines, degree-bounded spanning trees and multi-budgeted matchings.

Additional Metadata
Organisation	Networks and Optimization
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Bansal, N. (2018). On a generalization of iterated and randomized rounding.

View at arXiv

Free Full Text ( Final Version , 249kb )

See Also
inProceedings On a generalization of iterated and randomized rounding N. Bansal (Nikhil)

On a generalization of iterated and randomized rounding

Publication

Publication

inProceedings
On a generalization of iterated and randomized rounding

Address

Publishing at CWI

Questions or comments?

On a generalization of iterated and randomized rounding

Publication

Publication

inProceedings On a generalization of iterated and randomized rounding

Workflow

Workflow

Add Content

inProceedings
On a generalization of iterated and randomized rounding