Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems

An intuitive solution-doubling argument establishes well known results conc erning the worst-case performance of spanning tree-based heuristics for the Steiner network problem and the traveling salesman problem, This note show s 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 telecommunication networks. We use the doubling s trategy to establish worst-case upper bounds on the value of tree-based heu ristics relative to the optimal value for some versions of the LCS problem, and also provide a tight lower bound based on solutions to matching proble ms, (C) 2001 Elsevier Science B.V. All rights reserved.