Premium
Probabilistic analysis of a network design problem heuristic
Author(s) -
Wong Richard T.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150306
Subject(s) - mathematical optimization , heuristic , constraint (computer aided design) , network planning and design , probabilistic logic , computer science , mathematics , budget constraint , euclidean geometry , artificial intelligence , computer network , geometry , neoclassical economics , economics
Previous work has shown the budget network design problem (selecting a subset of arcs, subject to a budget constraint, so that the total weighted sum of the shortest paths in the network is minimized) to be a very difficult optimization problem. This article gives an efficient heuristic procedure for solving budget network design problems embedded in a circle on the euclidean plane where the nodes are independently and randomly distributed over the circle. With mild conditions on the budget constraint, we prove that as the number of nodes increases, the probability that the heuristic solution value exceeds any fixed percentage of the optimal solution value goes to zero. Computational results for the heuristic arc given.