scientific article; zbMATH DE number 7651222

DOI10.4230/LIPICS.ESA.2020.83MaRDI QIDQ5874556FDOQ5874556

Authors: Xianghui Zhong 

Publication date: 7 February 2023

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

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (2)

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

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)