Optimal network design

The input to the optimal network design problem is a weighted graph G = (V,E), where the weight of each edge (u,v) in the graph represents the cost of building a road from u to v; and a budget B.

A feasible network is a subset S of E, such that the sum of w(u,v) for all (u,v) in S is at most B, and there is a path between every two nodes u and v (that is, S contains a spanning tree of G).

For each feasible network S, the total cost of S is the sum, over all pairs (u,v) in E, of the length of the shortest path from u to v, which uses only edges in S. The objective is to find a feasible network with a minimum total cost.

Johnson, Lenstra and Kan prove that the problem is NP-hard, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees.

Dionne and Florian studied branch and bound algorithms and showed that they work in a reasonable amount of time on medium-sized inputs but not on large inputs. Therefore, they presented heuristic approximation algorithms.

Anshelevic, Dasgupta, Tardos and Wexler study a game of network design, where every agent has a set of terminals and wants to build a network in which his terminals are connected, but pay as little as possible. They study the computational problem of checking whether a Nash equilibrium exists. For some special cases, they give a polynomial time algorithm that finds a (1+ε)-approximate Nash equilibrium.

Boffey and Hinxman present a heuristic method, and show that it yields high quality results. They also study solution methods based on branch-and-Bound, and evaluate the effects of making various approximations when calculating lower bounds. They also generalize the problem to networks with link construction cost not proportional to length, and with trip demands that are not all equal.