Approximation result toward nearest neighbor heuristic

DOI10.2298/YJOR0201011MzbMATH Open1045.90089OpenAlexW2018450565MaRDI QIDQ4452815FDOQ4452815

Authors: Jérôme Monnot 

Publication date: 2 March 2004

Published in: Yugoslav Journal of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2298/yjor0201011m

Recommendations

• On the nearest neighbor rule for the metric traveling salesman problem
• scientific article; zbMATH DE number 3869068
• On the nearest-neighbor algorithm for the mean-field traveling salesman problem
• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP

zbMATH Keywords

approximate algorithmsperformance ratiotravelling salesman

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cited In (7)

• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• Toward optimal \(\epsilon\)-approximate nearest neighbor algorithms
• Worst case analysis of nearest neighbour algorithms for the minimum weighted directed \(k\)-cycle problem
• The bright side of simple heuristics for the TSP
• Nearest-neighbour heuristics in accelerated algorithms of optimisation problems
• On the nearest neighbor rule for the metric traveling salesman problem
• Analysis of an adaptive algorithm to find the two nearest neighbors

This page was built for publication: Approximation result toward nearest neighbor heuristic

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