2009-20: Statistics for a Random Network Design Problem

DIMACS TR: 2009-20

Statistics for a Random Network Design Problem

Authors: Fred J. Rispoli and Steven Cosares

ABSTRACT
We investigate a random network design problem specified by a complete graph with n nodes whose edges have associated fixed costs that are independent random variables, and variable costs that are also independent random variables. The objective is to find a spanning tree whose total fixed cost plus total variable cost is minimum, where the total variable cost is the sum of variable costs along paths from a source node to every other node. Here we examine the distributions of total fixed cost, total variable and total cost obtained from random tree generation. In particular, we compare potential heuristic solutions such as the minimum spanning tree, the shortest paths tree and the best tree obtained from random tree generation.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-20.pdf

DIMACS Home Page