Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Friedrich, Tobias | de |
dc.contributor.author | Hebbinghaus, Nils | de |
dc.contributor.author | He, Jun | de |
dc.contributor.author | Neumann, Frank | de |
dc.contributor.author | Witt, Carsten | de |
dc.date.accessioned | 2009-05-12T16:01:08Z | - |
dc.date.available | 2009-05-12T16:01:08Z | - |
dc.date.issued | 2007-02 | de |
dc.identifier.uri | http://hdl.handle.net/2003/26131 | - |
dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-8706 | - |
dc.description.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. | en |
dc.language.iso | en | de |
dc.relation.ispartofseries | Reihe CI; 224-07 | de |
dc.subject.ddc | 004 | de |
dc.title | Approximating covering problems by randomized search heuristics using multi-objective models | en |
dc.type | Text | de |
dc.type.publicationtype | report | de |
dcterms.accessRights | open access | - |
Appears in Collections: | Sonderforschungsbereich (SFB) 531 |
This item is protected by original copyright |
This item is protected by original copyright rightsstatements.org