The Lazy Matroid Problem
Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2014), The Lazy Matroid Problem, in Diaz, Josep; Lanese, Ivan; Sangiorgi, Davide, Theoretical Computer Science, Springer : Berlin Heidelberg, p. 66-77. 10.1007/978-3-662-44602-7_6
Type
Communication / ConférenceDate
2014Conference title
8th IFIP TC 1/WG 2.2 International Conference, TCS 2014Conference date
2014-09Conference city
RomeConference country
ItalyBook title
Theoretical Computer ScienceBook author
Diaz, Josep; Lanese, Ivan; Sangiorgi, DavidePublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-662-44601-0
Number of pages
354Pages
66-77
Publication identifier
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pagourtzis, Aris T.
School of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Abstract (EN)
This 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.Subjects / Keywords
approximation algorithms; matroids; independent dominating setRelated items
Showing items related by title and author.
-
The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2013) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2013) Communication / Conférence
-
Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2020) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2022) Article accepté pour publication ou publié