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.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com