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 salesmancomplete digraph\(k\)-person travelling salesmanminimum length closed walkpatching algorithm

Mathematics Subject Classification ID

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

Related Items (5)

On the relationship between ATSP and the cycle cover problem ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ 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 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

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