The Lazy Matroid Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

The Lazy Matroid Problem

Résumé

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.
Fichier principal
Vignette du fichier
978-3-662-44602-7_6_Chapter.pdf (187.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01402029 , version 1 (24-11-2016)

Licence

Paternité

Identifiants

Citer

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⟩
145 Consultations
126 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More