Approximation result toward nearest neighbor heuristic

DOI10.2298/YJOR0201011MMaRDI QIDQ4452815zbMATHOpenAlexFDO

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

zbMATH Keywords

approximate algorithmsperformance ratiotravelling salesman

Mathematics Subject Classification ID

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

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

Cited in

(7)

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

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)