On patching algorithms for random asymmetric travelling salesman problems

DOI10.1007/BF01585751zbMath0742.90064WikidataQ56324130 ScholiaQ56324130MaRDI QIDQ1813831

Martin Dyer, Alan M. Frieze

Publication date: 25 June 1992

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

zbMATH Keywords

travelling salesman; complete digraph; \(k\)-person travelling salesman; minimum length closed walk; patching algorithm

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal, Random shortest paths: non-Euclidean instances for metric optimization problems, 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

Cites Work

• The shortest-path problem for graphs with random arc-lengths
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Probability Inequalities for Sums of Bounded Random Variables
• Unnamed Item
• Unnamed Item