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.
Friedrich
Tobias
T
Max-Planck-Institut für Informatik, Saarbrücken, Germany. tobias.friedrich@mpi-inf.mpg.de
He
Jun
J
Hebbinghaus
Nils
N
Neumann
Frank
F
Witt
Carsten
C
D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical; D011336:Probability; D057386:Search Engine