The simultaneous semi-random model for TSP
From MaRDI portal
Publication:2164675
DOI10.1007/978-3-031-06901-7_4zbMath1497.90163OpenAlexW4285240125MaRDI QIDQ2164675
Mathieu Kubik, Yuri Faenza, Eric Balkanski
Publication date: 16 August 2022
Full work available at URL: https://doi.org/10.1007/978-3-031-06901-7_4
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the solution of traveling salesman problems
- The Euclidean traveling salesman problem is NP-complete
- Heuristics for semirandom graph problems
- Worst-case analysis of a new heuristic for the travelling salesman problem
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Removing and Adding Edges for the Traveling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Smoothed analysis of algorithms
- TSPLIB—A Traveling Salesman Problem Library
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- Coloring Random and Semi-Random k-Colorable Graphs
- Smoothed Analysis of the 2-Opt Algorithm for the General TSP
- A PTAS for Euclidean TSP with Hyperplane Neighborhoods
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Beyond the Worst-Case Analysis of Algorithms
- Approaching 3/2 for the s - t -path TSP
- An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- On the effect of randomness on planted 3-coloring models
- Solution of a Large-Scale Traveling-Salesman Problem
- Approximation algorithms for semi-random partitioning problems
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- A (slightly) improved approximation algorithm for metric TSP
This page was built for publication: The simultaneous semi-random model for TSP
