• 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 - No thumbnail

Object Allocation and Positive Graph Externalities

Fotakis, Dimitris; Gourvès, Laurent; Kasouridis, Stelios; Pagourtzis, Aris (2020), Object Allocation and Positive Graph Externalities, ECAI 2020, the 24th European Conference on Artificial Intelligence, 2020-08, Santiago de Compostela, SPAIN

View/Open
871_paper.pdf (320.6Kb)
Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-03037335
Date
2020
Conference title
ECAI 2020, the 24th European Conference on Artificial Intelligence
Conference date
2020-08
Conference city
Santiago de Compostela
Conference country
SPAIN
Metadata
Show full item record
Author(s)
Fotakis, Dimitris
Gourvès, Laurent
Kasouridis, Stelios
Pagourtzis, Aris
Abstract (EN)
The worth of an entity does not only come from its intrinsic value. The other entities in the neighborhood also influence this quantity. We introduce and study a model where some heterogeneous objects have to be placed on a network so that the elements with high value may exert a positive externality on neighboring elements whose value is lower. We aim at maximizing this positive influence called graph externality. By exploiting a connection with the minimum dominating set problem, we prove that the problem is NP-hard when the maximum degree is 3, but polynomial time solvable when the maximum degree is 2. We also present exact and approximation algorithms for special cases. In particular, if only two valuations exist, then a natural greedy strategy, which works well for maximum coverage problems, leads to a constant approximation algorithm. With extensive numerical experiments we finally show that a greedy algorithm performs very well for general valuations.

Related items

Showing items related by title and author.

  • Thumbnail
    Covering Clients with Types and Budgets 
    Fotakis, Dimitris; Gourvès, Laurent; Mathieu, Claire; Srivastav, Abhinav (2018) Communication / Conférence
  • Thumbnail
    Conference Program Design with Single-Peaked and Single-Crossing Preferences 
    Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
  • Thumbnail
    The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design 
    Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2013) Communication / Conférence
  • Thumbnail
    Selfish Transportation Games 
    Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2017) Communication / Conférence
  • Thumbnail
    The Lazy Matroid Problem 
    Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2014) 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