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

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

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial analysis, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.