{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:00:46Z","timestamp":1778601646007,"version":"3.51.4"},"reference-count":7,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1162\/evco_a_00003","type":"journal-article","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T17:21:14Z","timestamp":1277745674000},"page":"617-633","source":"Crossref","is-referenced-by-count":95,"title":["Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models"],"prefix":"10.1162","volume":"18","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"He","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Wales, Aberystwyth, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nils","family":"Hebbinghaus","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[{"name":"DTU Informatics, Technical University of Denmark, Kgs. Lyngby, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2004.841903"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1109\/4235.974841"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2004.823470"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-006-9004-x"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:57:51Z","timestamp":1615586271000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/18\/4\/617-633\/1352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1162\/EVCO_a_00003"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00003","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}