Journal article
Approximating covering problems by randomized search heuristics using multi-objective models
The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems.
For the VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multi-objective approach, while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.
Language: | English |
---|---|
Publisher: | MIT Press |
Year: | 2010 |
Pages: | 617-633 |
ISSN: | 15309304 and 10636560 |
Types: | Journal article |
DOI: | 10.1162/EVCO_a_00003 |
ORCIDs: | Witt, Carsten |