All publications

EUCLID / RESEARCH OUTPUT

Book Chapter

Combinatorial Randomized Rounding: Boosting Randomized Rounding with Combinatorial Arguments

Pavlos S. Efraimidis, Paul G. Spirakis

Applied Optimization · 2001

Abstract

Randomized Rounding (RR) is a simple and very efficient probabilistic method to convert a solution of a relaxed combinatorial optimization (CO) problem into an approximate solution to the original problem. Since its introduction by Raghavan and Thompson in [14], RR and variations of it have been successfully applied to many approximation algorithms for hard CO problems. Though RR can be applied to an even wider set of problems, often the performance guarantees of the RR based approximation algorithms are poor.

CITATION

BibTeX

Efraimidis_2001 
@inbook{Efraimidis_2001,
    title={Combinatorial Randomized Rounding: Boosting Randomized Rounding with Combinatorial Arguments},
    ISBN={9781475765946},
    ISSN={1384-6485},
    url={http://dx.doi.org/10.1007/978-1-4757-6594-6_2},
    DOI={10.1007/978-1-4757-6594-6_2},
    booktitle={Stochastic Optimization: Algorithms and Applications},
    publisher={Springer US},
    author={Efraimidis, Pavlos S. and Spirakis, Paul G.},
    year={2001},
    pages={31–53}
}
Back to publications