On-line models for set-covering: the power of greediness

dc.contributor.author	Ausiello, Giorgio
dc.contributor.author	Giannakos, Aristotelis
dc.contributor.author	Paschos, Vangelis
dc.date.accessioned	2012-07-11T15:05:09Z
dc.date.available	2012-07-11T15:05:09Z
dc.date.issued	2006
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/9728
dc.language.iso	en	en
dc.subject	set-covering	en
dc.subject.ddc	003	en
dc.title	On-line models for set-covering: the power of greediness	en
dc.type	Document de travail / Working paper
dc.description.abstracten	We 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.name	Université Paris-Dauphine	en
dc.publisher.city	Paris	en
dc.identifier.citationpages	17	en
dc.relation.ispartofseriestitle	Cahier du LAMSADE	en
dc.relation.ispartofseriesnumber	235	en
dc.description.sponsorshipprivate	oui	en
dc.subject.ddclabel	Recherche opérationnelle	en

Related items