Show simple item record

A survey of approximately optimal solutions to some covering and packing problems

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-30T09:48:33Z
dc.date.available2010-04-30T09:48:33Z
dc.date.issued1997
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4063
dc.language.isoenen
dc.subjectCombinatorial optimizationen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleA survey of approximately optimal solutions to some covering and packing problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex covering, the maximum set packing, and maximum independent set problems; we discuss their approximation performance and their complexity. For already known results, any time we have conceived simpler proofs than those already published, we give these proofs, and, for the rest, we cite the simpler published ones. Finally, we discuss how one can relate the approximability behavior (from both a positive and a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems.en
dc.relation.isversionofjnlnameACM Computing Surveys
dc.relation.isversionofjnlvol29en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate1997-06
dc.relation.isversionofjnlpages171-209en
dc.relation.isversionofdoihttp://doi.acm.org/10.1145/254180.254190en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherACMen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record