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
TypeCommunication / Conférence
External document linkhttps://hal.archives-ouvertes.fr/hal-03037335
Conference titleECAI 2020, the 24th European Conference on Artificial Intelligence
Conference citySantiago de Compostela
MetadataShow full item record
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.
Showing items related by title and author.