On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem

DOI10.1239/jap/1395771417zbMath1321.90114arXiv1206.6991OpenAlexW2002721235MaRDI QIDQ5416544

Farkhondeh Sajadi, Antar Bandyopadhyay

Publication date: 14 May 2014

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.6991

zbMATH Keywords

traveling salesman problemmean-field setupnearest-neighbor algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Processes in random environments (60K37) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Replica symmetry of the minimum matching
• The mean field traveling salesman and related problems
• Probability for Statistics and Machine Learning
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• The Traveling Salesman Problem: A Survey