A Randomized Rounding Approach to the Traveling Salesman Problem

DOI10.1109/FOCS.2011.80zbMath1292.68171OpenAlexW2038652993MaRDI QIDQ5494986

Amin Saberi, Shayan Oveis Gharan, Mohit Singh

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.80

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (54)

Generalized maximum entropy estimation ⋮ Traveling salesman problems in temporal graphs ⋮ A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs ⋮ Paving property for real stable polynomials and strongly Rayleigh processes ⋮ Random Walks in Polytopes and Negative Dependence ⋮ The Steiner traveling salesman problem with online edge blockages ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ Better s-t-Tours by Gao Trees ⋮ Constant Factor Approximation for ATSP with Two Edge Weights ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Approximation hardness of graphic TSP on cubic graphs ⋮ Matroid-based TSP rounding for half-integral solutions ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ On tail triviality of negatively dependent stochastic processes ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ The Poisson binomial distribution -- old \& new ⋮ Amalgamation of real zero polynomials ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ The minimum spanning tree problem with non-terminal set ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ The traveling salesman problem on cubic and subcubic graphs ⋮ The salesman's improved tours for fundamental classes ⋮ Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ New inapproximability bounds for TSP ⋮ TSP on Cubic and Subcubic Graphs ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ Unnamed Item ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ The temporal explorer who returns to the base ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Nonoblivious 2-Opt heuristics for the traveling salesman problem ⋮ An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs ⋮ Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ On the integrality gap of the subtour LP for the 1,2-TSP ⋮ Reducing Path TSP to TSP ⋮ Unnamed Item ⋮ Approximating TSP walks in subcubic graphs ⋮ Unnamed Item ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ Approximating minimum-cost connected \(T\)-joins ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

This page was built for publication: A Randomized Rounding Approach to the Traveling Salesman Problem