scientific article; zbMATH DE number 7651222

DOI10.4230/LIPICS.ESA.2020.83MaRDI QIDQ5874556zbMATH OpenFDO

Authors Xianghui Zhong

Publication date 7 February 2023

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

zbMATH Keywords

approximation algorithmtraveling salesman problemmetric TSPLin-Kernighan algorithm\(k\)-opt algorithmapproximation ratio.graph TSP

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP
• Approximating the Metric TSP in Linear Time
• Approximating the metric TSP in linear time
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• A (slightly) improved approximation algorithm for metric TSP
• Approximating the regular graphic TSP in near linear time
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• scientific article; zbMATH DE number 1003245
• The approximation ratio of the greedy algorithm for the metric traveling salesman problem

Cites work

• scientific article; zbMATH DE number 4031430 (Why is no real title available?)
• scientific article; zbMATH DE number 177832 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• A new series of dense graphs of high girth
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Combinatorial optimization. Theory and algorithms.
• Decompositions into subgraphs of small diameter
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Fast Algorithms for Geometric Traveling Salesman Problems
• Minimal Regular Graphs of Girths Eight and Twelve
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Nonoblivious 2-opt heuristics for the traveling salesman problem
• On Graphs that do not Contain a Thomsen Graph
• On Minimal graphs of maximum even girth
• Reducibility among combinatorial problems
• The Moore bound for irregular graphs
• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• The design of approximation algorithms
• The traveling salesman. Computational solutions for RSP applications
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

Cited in

(3)

• On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP
• On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem

This page was built for publication:

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