Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorSerrière, Fabrice
dc.date.accessioned2010-03-09T14:54:43Z
dc.date.available2010-03-09T14:54:43Z
dc.date.issued2005
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3677
dc.language.isoenen
dc.subjectComplexity
dc.subjectApproximation algorithms
dc.subjectGreedy algorithm
dc.subjectSet cover
dc.subjectCombinatorial problem
dc.subject.ddc511en
dc.titleOn the differential approximation of MIN SET COVER
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by 1.365/Δ and above by 4/(Δ+1), where Δ is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by 2/(Δ+1) and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of 1/Δ. Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol332
dc.relation.isversionofjnlissue1-3
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages497-513
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2004.12.022
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:48:32Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record