Heuristics, LPs, and trees on trees: Network design analyses

• 成果类型: Article
• 署名作者: Balakrishnan, A; Magnanti, TL; Mirchandani, P
• 署名单位: Massachusetts Institute of Technology (MIT); Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.44.3.478
• 发表日期: 1996
• 页码: 478-496

摘要

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 far various new multi-tier, survivable network design models that incorporate both multiple facility types and differential node connectivity levels.