Article ID: | iaor20021959 |
Country: | Netherlands |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 99 |
End Page Number: | 106 |
Publication Date: | Oct 2001 |
Journal: | Operations Research Letters |
Authors: | Balakrishnan Anantaram, Magnanti Thomas L., Mirchandani Prakash |
Keywords: | combinatorial analysis, programming: travelling salesman |
An intuitive solution-doubling argument establishes well known results concerning the worst-case performance of spanning tree-based heuristics for the Steiner network problem and the traveling salesman problem. This note shows that the solution-doubling argument and its implications apply to certain more general Low Connectivity Steiner (LCS) problems that are important in the design of survivable telecommunications networks. We use the doubling strategy to establish worst-case upper bounds on the value of tree-based heuristics relative to the optimal value for some versions of the LCS problem, and also provide a tight lower bound based on solutions to matching problems.