Show simple item record

The Lazy Matroid Problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
hal.structure.identifierSchool of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
dc.contributor.authorPagourtzis, Aris T.
dc.date.accessioned2017-01-07T15:36:23Z
dc.date.available2017-01-07T15:36:23Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16134
dc.descriptionin Springer series Lecture Notes in Computer Science, vol. 8705en
dc.language.isoenen
dc.subjectapproximation algorithmsen
dc.subjectmatroidsen
dc.subjectindependent dominating seten
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleThe Lazy Matroid Problemen
dc.typeCommunication / Conférence
dc.description.abstractenThis article introduces the lazy matroid problem, which captures the goal of saving time or money in certain task selection scenarios. We are given a budget B and a matroid M with weights on its elements. The problem consists in finding an independent set F of minimum weight. In addition, F is feasible if its augmentation with any new element x implies that either F + x exceeds B or F + x is dependent. Our first result is a polynomial time approximation scheme for this NP-hard problem which generalizes a recently studied version of the lazy bureaucrat problem. We next study the approximability of a more general setting called lazy staff matroid. In this generalization, every element of M has a multidimensional weight. We show that approximating this generalization is much harder than for the lazy matroid problem since it includes the independent dominating set problem.en
dc.identifier.citationpages66-77en
dc.relation.ispartoftitleTheoretical Computer Scienceen
dc.relation.ispartofeditorDiaz, Josep
dc.relation.ispartofeditorLanese, Ivan
dc.relation.ispartofeditorSangiorgi, Davide
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2014
dc.relation.ispartofpages354en
dc.relation.ispartofurl10.1007/978-3-662-44602-7en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-662-44601-0en
dc.relation.conftitle8th IFIP TC 1/WG 2.2 International Conference, TCS 2014en
dc.relation.confdate2014-09
dc.relation.confcityRomeen
dc.relation.confcountryItalyen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-662-44602-7_6en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-07T15:23:25Z
hal.faultCode{"duplicate-entry":{"hal-01402029":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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