scientific article; zbMATH DE number 7651222
From MaRDI portal
Publication:5874556
DOI10.4230/LIPIcs.ESA.2020.83MaRDI QIDQ5874556
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/1909.12755
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
approximation algorithmtraveling salesman problemmetric TSPLin-Kernighan algorithm\(k\)-opt algorithmapproximation ratio.graph TSP
Related Items (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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- The traveling salesman. Computational solutions for RSP applications
- The Moore bound for irregular graphs
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
- Nonoblivious 2-Opt heuristics for the traveling salesman problem
- The Design of Approximation Algorithms
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- Reducibility Among Combinatorial Problems
- Fast Algorithms for Geometric Traveling Salesman Problems
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- A new series of dense graphs of high girth
- Decompositions into Subgraphs of Small Diameter
- Minimal Regular Graphs of Girths Eight and Twelve
- On Minimal graphs of maximum even girth
- On Graphs that do not Contain a Thomsen Graph
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Combinatorial optimization. Theory and algorithms.
This page was built for publication:
