Worst case analysis of nearest neighbour algorithms for the minimum weighted directed k-cycle problem

MaRDI QIDQ3385394zbMATH OpenFDO

Authors Piyashat Sripratak

Publication date 18 December 2021

Full work available at URL http://thaijmath.in.cmu.ac.th/index.php/thaijmath/article/view/4590

zbMATH Keywords

worst case analysisgreedy heuristicminimum weightk-cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
• Approximation result toward nearest neighbor heuristic
• On the nearest neighbor rule for the metric traveling salesman problem

Cites work

• scientific article; zbMATH DE number 3604272 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 1893558 (Why is no real title available?)
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Dominance guarantees for above-average solutions
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• The traveling salesman problem. A computational study.
• The traveling salesman. Computational solutions for RSP applications
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• \(z\)-approximations

Cited in

(1)

• Weighted nearest neighbor algorithms for the graph exploration problem on cycles

This page was built for publication: Worst case analysis of nearest neighbour algorithms for the minimum weighted directed \(k\)-cycle problem

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