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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.66-77, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_6〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402029
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:48:25
Dernière modification le : jeudi 11 janvier 2018 - 06:17:30
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:59:46

Fichier

978-3-662-44602-7_6_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Laurent Gourvès, Jérôme Monnot, Aris Pagourtzis. The Lazy Matroid Problem. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.66-77, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_6〉. 〈hal-01402029〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

11