Authors: Friedrich, Tobias
Hebbinghaus, Nils
He, Jun
Neumann, Frank
Witt, Carsten
Title: Approximating covering problems by randomized search heuristics using multi-objective models
Language (ISO): en
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 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 Set-Cover 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.
URI: http://hdl.handle.net/2003/26131
http://dx.doi.org/10.17877/DE290R-8706
Issue Date: 2007-02
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
22407.pdfDNB215.81 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.