pdf icon
Volume 20 (2024) Article 6 pp. 1-23
On a Generalization of Iterated and Randomized Rounding
Received: April 24, 2019
Revised: November 18, 2022
Published: December 5, 2024
Download article from ToC site:
[PDF (350K)] [PS (1612K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: approximation, randomized rounding, scheduling, discrepancy, semidefinite programming, random walks
Categories: algorithms, approximation algorithms, randomized rounding, scheduling, discrepancy, semidefinite programming, random walks
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25, 68W20

Abstract: [Plain Text Version]

$ $

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).