title: Approximating covering problems by randomized search heuristics using multi-objective models.
abstract: 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.
authors.affiliation: Max-Planck-Institut für Informatik, Saarbrücken, Germany. tobias.friedrich@mpi-inf.mpg.de
authors.forename: Tobias
authors.initials: T
authors.lastname: Friedrich
authors.forename: Jun
authors.initials: J
authors.lastname: He
authors.forename: Nils
authors.initials: N
authors.lastname: Hebbinghaus
authors.forename: Frank
authors.initials: F
authors.lastname: Neumann
authors.forename: Carsten
authors.initials: C
authors.lastname: Witt
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical; D011336:Probability; D057386:Search Engine