Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

Research output: Contribution to journalArticlepeer-review

96 Citations (SciVal)

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.
Original languageEnglish
Pages (from-to)617-633
JournalEvolutionary Computation
Volume18
Issue number4
Early online date24 Nov 2010
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models'. Together they form a unique fingerprint.

Cite this