On patching algorithms for random asymmetric travelling salesman problems

DOI10.1007/BF01585751MaRDI QIDQ1813831zbMATH OpenWikidataFDO

Authors Martin Dyer, Alan Frieze

Publication date 25 June 1992

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01585751

zbMATH Keywords

\(k\)-person travelling salesmancomplete digraphminimum length closed walkpatching algorithmtravelling salesman

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

Let the arc-lengths \(\ell_{ij}\) of a complete digraph of order \(n\) be independent uniform \([0,1]\) random variables. The authors consider the patching algorithm of \textit{R. M. Karp} [SIAM J. Comput. 8, 561-573 (1979; Zbl 0427.90064)] and \textit{R. M. Karp} and \textit{J. M. Steele} [in: The travelling salesman problem, a guided tour of combinatorial optimization, 181-205 (1985; Zbl 0582.90100)] for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. These ideas are also extended to the \(k\)-person travelling salesman problem [see \textit{G. Frederickson, M. Hecht} and \textit{C. Kim}, SIAM J. Comput. 7, 178-193 (1978)] and the problem of finding the minimum length closed walk through the vertex set of the digraph.

Recommendations

• Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem
• Domination analysis of some heuristics for the traveling salesman problem
• On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients
• On Random Symmetric Travelling Salesman Problems
• On some applications of the patching method

Cites work

• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3908167 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• The shortest-path problem for graphs with random arc-lengths

Cited in

(11)

• Reduction techniques providing initial groupings for Euclidean traveling salesman patching algorithms
• Iterative patching and the asymmetric traveling salesman problem
• On some applications of the patching method
• Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem
• Combining GLSP and ATSP approaches to lot sizing and sequencing in the production of animal feed supplements
• On Random Symmetric Travelling Salesman Problems
• Solving a random asymmetric TSP exactly in quasi-polynomial time w.h.p.
• Hamilton cycles in random digraphs with minimum degree at least one
• On the relationship between ATSP and the cycle cover problem
• Random assignment problems
• Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching

This page was built for publication: On patching algorithms for random asymmetric travelling salesman problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813831)