HEURISTICS, LPS, AND TREES ON TREES - NETWORK DESIGN ANALYSES

We study a class of models, known as overlay optimization problems, co mposed of ''base'' and ''overlay'' subproblems, linked by the requirem ent that the overlay solution be contained in the base solution In som e telecommunication settings, a feasible base solution is a spanning t ree, and the overlay solution is an embedded Steiner tree or path. For the general overlay optimization problem, we describe a composite heu ristic solution procedure that selects the better of two feasible solu tions obtained by independently solving the base and the overlay subpr oblems, and establish worst-case performance guarantees (as a function of the worst-case bounds for the subproblems) for the composite heuri stic as well as an LP relaxation of the model. For certain special cas es, both the heuristic and the LP relaxation have a worst-case bound o f 4/3. We extend this analysis to multiple overlays on the same base s olution, producing the first known worst-case bounds (approximately pr oportional to the square root of the number of commodities) for the un capacitated multicommodity network design problem. In a companion pape r, we develop heuristic performance guarantees far various new multi-t ier, survivable network design models that incorporate both multiple f acility types and differential node connectivity levels.