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
Type
Communication / ConférenceExternal document link
https://hal.archives-ouvertes.fr/hal-03037335Date
2020Conference title
ECAI 2020, the 24th European Conference on Artificial IntelligenceConference date
2020-08Conference city
Santiago de CompostelaConference country
SPAINMetadata
Show full item recordAbstract (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.
-
Fotakis, Dimitris; Gourvès, Laurent; Mathieu, Claire; Srivastav, Abhinav (2018) Communication / Conférence
-
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
-
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
-
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2017) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Pagourtzis, Aris T. (2014) Communication / Conférence