neal young / Young95Randomized

Randomized rounding is a standard method, based on the probabilistic method, for designing combinatorial approximation algorithms. This paper introduces a variant of randomized rounding that can be used to derive Lagrangianrelaxation algorithms and greedy algorithms. This was surprising  the approximation algorithms derived previously by the method require first solving a linear program (or some other optimization problem). Indeed, in Prabhakar Raghavan's seminal paper introducing randomized rounding [1988], he says: "The time taken to solve the linear program relaxations of the integer programs dominates the net running time theoretically (and, most likely, in practice as well)."
The variant of randomized rounding described here avoids this bottleneck, at least for packing/coveringtype problems. The resulting algorithms are Lagrangianrelaxation algorithms and greedy algorithms (in fact the greedy setcover algorithm is an example), and are faster and simpler to implement than standard randomizedrounding algorithms. This approach gives a systematic, coherent, and comprehensive understanding of Lagrangianrelaxation algorithms for packing and covering linear programs.
The ideas introduced here are also used in ``Sequential and parallel algorithms for mixed packing and covering'' [2001], in ``Kmedians, facility location, and the ChernoffWald bound'' [2000]), and in ``On the number of iterations for DantzigWolfe optimization and packingcovering approximation algorithms'' [1999].Lecture notes on this topic are here.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.