A. Balakrishnan et al., Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, OPER RES L, 29(3), 2001, pp. 99-106
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.