Near-optimal tree-based access network design

Among various access network topologies, the tree topology is the most popular due to its simplicity and relatively low cost. A salient
example is the CATV network. In this paper, we consider the tree-based access network design problem where the operational cost and the
fixed installation cost are jointly minimized. The problem is formulated as a combinatorial optimization problem, where the difficulty of
solving a Steiner tree problem typically encountered in a tree-based topological design problem is particularly circumvented. The basic
approach to the algorithm development is Lagrangean relaxation and the subgradient method. In the computational experiments, the
proposed algorithm calculates near-optimal solutions within 3.2% of an optimal solution in 1 min of CPU time for test networks of up to
26 nodes.