The simultaneous semi-random model for TSP

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

Eric Balkanski, Mathieu Kubik, Yuri Faenza

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)

Cites Work

• TSPLIB—A Traveling Salesman Problem Library
• A Dynamic Programming Approach to Sequencing Problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Euclidean traveling salesman problem is NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Smoothed analysis of algorithms
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Title not available (Why is that?)
• Beyond the Worst-Case Analysis of Algorithms
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• A (slightly) improved approximation algorithm for metric TSP
• An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• Heuristics for semirandom graph problems
• Coloring Random and Semi-Random k-Colorable Graphs
• 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
• Removing and Adding Edges for the Traveling Salesman Problem
• Approaching 3/2 for the s - t -path TSP
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Smoothed Analysis of the 2-Opt Algorithm for the General TSP
• A PTAS for Euclidean TSP with Hyperplane Neighborhoods
• On the effect of randomness on planted 3-coloring models

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)