-
Views
-
Cite
Cite
Alexander Gutfraind, Jeremy Kun, Ádám D. Lelkes, Lev Reyzin, Network installation under convex costs, Journal of Complex Networks, Volume 4, Issue 2, June 2016, Pages 177–186, https://doi.org/10.1093/comnet/cnv020
- Share Icon Share
Abstract
We study the Neighbour-Aided Network Installation Problem (NANIP) introduced previously which asks for a minimal cost ordering of the nodes of a graph, where the cost of visiting a node is a function of the number of its neighbours that have already been visited. This problem has applications in resource management and disaster recovery. In this paper, we analyse the computational hardness of NANIP. In particular we show that this problem is NP-hard even when restricted to convex decreasing cost functions, give a linear approximation lower bound for the greedy algorithm, and prove a general sub-constant approximation lower bound. Then we give a new integer programming formulation of NANIP and empirically observe its speedup over the original integer programme.