Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-027 | 2nd February 2007 00:00

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 results on this subject.
We consider the approximation ability of randomized search 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 even no good approximation can be achieved within expected polynomial time. Examining the more general SetCover problem we show that optimal solutions can be approximated within a factor of log(n), where n is the problem dimension using the multi-objective approach while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.

ISSN 1433-8092 | Imprint