The simultaneous semi-random model for TSP

DOI10.1007/S10107-023-02011-WMaRDI QIDQ6589752FDOQ6589752

Authors Eric Balkanski, Yuri Faenza, Mathieu Kubik

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

local searchtraveling salesman problembeyond worst-case analysissemi-random models

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• The simultaneous semi-random model for TSP
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed analysis of the 2-Opt algorithm for the general TSP
• Smoothed Analysis of Local Search

Cites work

• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A (slightly) improved approximation algorithm for metric TSP
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Approximation algorithms for semi-random partitioning problems
• Beyond the Worst-Case Analysis of Algorithms
• Coloring Random and Semi-Random k-Colorable Graphs
• Heuristics for semirandom graph problems
• How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• On the effect of randomness on planted 3-coloring models
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Removing and adding edges for the traveling salesman problem
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Smoothed analysis of algorithms
• Smoothed analysis of the 2-Opt algorithm for the general TSP
• Solution of a Large-Scale Traveling-Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• The Euclidean traveling salesman problem is NP-complete
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method

This page was built for publication: The simultaneous semi-random model for TSP

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