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 ones oil 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 even no good approximation call be achieved within expected polynomial time. Examining the more, general SETCOVER problem we show that, optimal solutions call he 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.