Heuristics, LPs, and Trees on Trees: Network Design Analyses

We study a class of models, known as overlay optimization problems, composed of “base” and “overlay” subproblems, linked by the requirement that the overlay solution be contained in the base solution. In some telecommunication settings, a feasible base solution is a spanning tree, and the overlay solution is an embedded Steiner tree or path. For the general overlay optimization problem, we describe a composite heuristic solution procedure that selects the better of two feasible solutions obtained by independently solving the base and the overlay subproblems, and establish worst-case performance guarantees (as a function of the worst-case bounds for the subproblems) for the composite heuristic as well as an LP relaxation of the model. For certain special cases, both the heuristic and the LP relaxation have a worst-case bound of 4/3. We extend this analysis to multiple overlays on the same base solution, producing the first known worst-case bounds (approximately proportional to the square root of the number of commodities) for the uncapacitated multicommodity network design problem. In a companion paper, we develop heuristic performance guarantees for various new multi-tier, survivable network design models that incorporate both multiple facility types and differential node connectivity levels.