Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorGiannakos, Aristotelis
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2012-07-11T15:05:09Z
dc.date.available2012-07-11T15:05:09Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9728
dc.language.isoenen
dc.subjectset-coveringen
dc.subject.ddc003en
dc.titleOn-line models for set-covering: the power of greedinessen
dc.typeDocument de travail / Working paper
dc.description.abstractenWe study an on-line model for set-covering implying that elements of the ground set of size n arrive one-by-one and with any such element i, arrive also the names of the sets containing it in the fi nal instance. Any new element has to be processed irrevocably before the arrival of the next element. We study limits on the competitiveness of several greedy rules solving several alternatives of this basic model. For any of them we give lower and upper bounds for the competitive ratio achieved. We finally deal with the maximum budget saving problem. Here, an initial budget is allotted that is destined to cover the cost of an algorithm for solving set-covering and the objective is to maximize the savings on the initial budget.en
dc.publisher.nameUniversité Paris-Dauphineen
dc.publisher.cityParisen
dc.identifier.citationpages17en
dc.relation.ispartofseriestitleCahier du LAMSADEen
dc.relation.ispartofseriesnumber235en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record