Worst-Case Analysis of Network Design Problem Heuristics
Richard T. Wong · SIAM Journal on Algebraic and Discrete Methods · 1980
The Optimal Network problem (as defined by A. J. Scott, The optimal network problem : Some computational procedures, Trans. Res., Vol 3 (1969) pp. 201–210) consists of selecting a subset of arcs that minimizes the sum of the shortest paths between all nodes subject to a budget constraint. This paper considers the worst-case behavior of heuristics for this problem. Let n be the number of nodes in the network and $\varepsilon $ be a constant between 0 and 1. For a general class of Optimal Network Problems, we show that the question of finding a solution which is always less than $n^{1 - \varepsilon } $ times the optimal solution is $NP$-complete. This indicates that all polynomial-time heuristics for the problem most probably have poor worst-case performance. An upper bound for worst-case heuristic performance of 2n times the optimal solution is also derived. For a restricted version of the Optimal Network problem we describe a procedure whose maximum percentage of error is bounded by a constant.