Statistics for a Random Network Design Problem

Date Added: Sep 2009
Format: PDF

This paper 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 associated 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 all paths from a source node to every other node. Here this paper examine the distributions of total fixed cost and total variable cost obtained from random tree generation, and compares the expectations in solving the different components of a random network design problem using simulation.