• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

The Lazy Matroid Problem

Thumbnail
Date
2014
Notes
in Springer series Lecture Notes in Computer Science, vol. 8705
Dewey
Recherche opérationnelle
Sujet
approximation algorithms; matroids; independent dominating set
JEL code
C.C4.C44
DOI
http://dx.doi.org/10.1007/978-3-662-44602-7_6
Conference name
8th IFIP TC 1/WG 2.2 International Conference, TCS 2014
Conference date
09-2014
Conference city
Rome
Conference country
Italy
Book title
Theoretical Computer Science
Author
Diaz, Josep; Lanese, Ivan; Sangiorgi, Davide
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2014
Pages number
354
ISBN
978-3-662-44601-0
Book URL
10.1007/978-3-662-44602-7
URI
https://basepub.dauphine.fr/handle/123456789/16134
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pagourtzis, Aris T.
245158 School of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Type
Communication / Conférence
Item number of pages
66-77
Abstract (EN)
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 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 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.