• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

On the impact of local taxes in a set cover game

Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010), On the impact of local taxes in a set cover game, in Patt-Shamir, Boaz; Ekim, Tinaz, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings., Springer : Berlin, p. 2-13

View/Open
sirocco.pdf (188.2Kb)
Type
Communication / Conférence
Date
2010
Conference title
SIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity
Conference date
2010-06
Conference city
Sirince
Conference country
Turquie
Book title
Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.
Book author
Patt-Shamir, Boaz; Ekim, Tinaz
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
6058
Published in
Berlin
ISBN
978-3-642-13283-4
Pages
2-13; 15
Publication identifier
http://dx.doi.org/10.1007/978-3-642-13284-1_2
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Gourvès, Laurent
Escoffier, Bruno
Abstract (EN)
Given a collection C of weighted subsets of a ground set E, the set cover problem is to find a minimum weight subset of C which covers all elements of E. We study a strategic game defined upon this classical optimization problem. Every element of E is a player which chooses one set of C where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized.
Subjects / Keywords
Set cover; Optimization

Related items

Showing items related by title and author.

  • Thumbnail
    The Price of Optimum in a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2011) Communication / Conférence
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    The Price of Optimum: Complexity and Approximation for a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo