Skip to Main content Skip to Navigation
Conference papers

The Lazy Matroid Problem

Abstract : 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 ${\cal 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 ${\cal 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Thursday, November 24, 2016 - 10:48:25 AM
Last modification on : Tuesday, January 25, 2022 - 8:30:03 AM
Long-term archiving on: : Monday, March 20, 2017 - 8:59:46 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Laurent Gourvès, Jérôme Monnot, Aris T. Pagourtzis. The Lazy Matroid Problem. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.66-77, ⟨10.1007/978-3-662-44602-7_6⟩. ⟨hal-01402029⟩



Record views


Files downloads