×

zbMATH — the first resource for mathematics

On the nearest-neighbor algorithm for the mean-field traveling salesman problem. (English) Zbl 1321.90114
Summary: In this work we consider the mean-field traveling salesman problem, where the intercity distances are taken to be independent and identically distributed with some distribution \(F\). We consider the simplest approximation algorithm, namely, the nearest-neighbor algorithm, where the rule is to move to the nearest nonvisited city. We show that the limiting behavior of the total length of the nearest-neighbor tour depends on the scaling properties of the density of \(F\) at 0 and derive the limits for all possible cases of general \(F\).
MSC:
90C27 Combinatorial optimization
60K37 Processes in random environments
05C85 Graph algorithms (graph-theoretic aspects)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Bellmore, M. and Nemhauser, G. L. (1968). The traveling salesman problem: a survey. Operat. Res. 16, 538-558. · Zbl 0213.44604
[2] DasGupta, A. (2011). Probability for Statistics and Machine Learning . Springer, New York. · Zbl 1233.62001
[3] Gavett, J. W. (1965). Three heuristic rules for sequencing jobs to a single production facility. Manag. Sci. 11, B-166-B-176.
[4] Papadimitriou, C. H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity . Dover, Mineola, NY. · Zbl 0944.90066
[5] Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. M., II (1977). An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563-581. · Zbl 0364.90104
[6] Vannimenus, J. and Mézard, M. (1984). On the statistical mechanics of optimization problems of the travelling salesman type. J. Physique Lett. 45, 1145-1153.
[7] Wästlund, J. (2012). Replica symmetry of the minimum matching. Ann. Math. 175, 1061-1091. · Zbl 1262.91046
[8] Wästlund, J. (2010). The mean field traveling salesman and related problems. Acta Math. 204, 91-150. · Zbl 1231.90370
[9] Wendel, J. G. (1948). Note on the gamma function. Amer. Math. Monthly 55, 563-564.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.