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

https://hal.inria.fr/hal-01402029
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

File

978-3-662-44602-7_6_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

221

Files downloads

487