Linear programming relaxations, approximation algorithms and randomization: A unified view of covering problems
Dimitris Bertsimas, Rakesh Vohra · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
Our goal is to propose a unified method of approximation of integer programming problems. We show that the use of randomized rounding of linear programming relaxations of discrete optimization problems, but with nonlinear rounding functions and the use of dual information leads to a unified way of approximating NP-hard problems matching or improving upon the best known performance guarantees. We illustrate our methods using several examples: the set covering problem, facility location problems, network connectivity problems, survivable network design, the minimum multi-cut problem to name a few. In this way we illustrate a deeper connection between LP relaxations and approximation algorithms through the use of randomization.