| dc.description.abstract | This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks whose nodes have varying levels of importance:the more critical or higher level nodes require higher grade interconnections. Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the MLND problem seeks a connected design that minimizes total fixed cost while spanning all the nodes, and connecting nodes at each level via facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we describe alternative model formulations for this problem and analyze the worst-case performance for heuristics based upon Steiner and spanning tree computations. For one model that we consider, the heuristic worst-case bounds on the performance ratio are either 4/3 or the worst-case performance ratio p of the embedded Steiner tree heuristic. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of the problem. Keywords: Network design, integer programming, valid inequalities, worstcase analysis of heuristics. | en_US |
