Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorSerrière, Fabrice
dc.date.accessioned2011-01-04T13:30:25Z
dc.date.available2011-01-04T13:30:25Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5362
dc.language.isoenen
dc.subjectMin Set Cover
dc.subjectdifferential approximation
dc.subject.ddc005
dc.titleGreedy differential approximations for MIN SET COVER
dc.typeCommunication / Conférence
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/Delta and above by , where Delta is the maximum set-cardinality in the min set cover-instance. Next, we study an approximation algorithm for min weighted set cover and provide a tight lower bound of 1/Delta.
dc.identifier.citationpages62-71
dc.relation.ispartoftitleSOFSEM'05 : Theory and Practice of Computer Science
dc.relation.ispartofeditorVojtas, Peter
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2005
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProgrammation, logiciels, organisation des données
dc.relation.ispartofisbn978-3-540-24302-1
dc.relation.confcountrySLOVAKIA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:10:27Z


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