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

Anantaram Balakrishnan, Thomas L. Magnanti and Prakash Mirchandani
Additional contact information
Anantaram Balakrishnan: The Pennsylvania State University, University Park, Pennsylvania
Thomas L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
Prakash Mirchandani: University of Pittsburgh, Pittsburgh, Pennsylvania

Operations Research, 1996, vol. 44, issue 3, 478-496

Abstract: 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.

Keywords: communications; heuristics—network design with multiple grade facilities; programming; integer; heuristic; worst case analysis of composite heuristics; networks/graphs; Steiner trees and paths on trees (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.3.478 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:3:p:478-496

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().