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 <>
Submitted on : Thursday, November 24, 2016 - 10:48:25 AM
Last modification on : Wednesday, October 14, 2020 - 4:01:16 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 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