A Randomized Rounding Approach to the Traveling Salesman Problem

DOI10.1109/FOCS.2011.80MaRDI QIDQ5494986zbMATH OpenOpenAlexFDO

Authors Shayan Oveis Gharan, Amin Saberi, 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

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

Cited in

(70)

• Better \(s-t\)-tours by Gao trees
• Constant factor approximation for ATSP with two edge weights
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Approximating TSP walks in subcubic graphs
• Paving property for real stable polynomials and strongly Rayleigh processes
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• Weighted amplifiers and inapproximability results for travelling salesman problem
• Matroid-based TSP rounding for half-integral solutions
• Shorter tours and longer detours: uniform covers and a bit beyond
• The salesman's improved tours for fundamental classes
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• \(\frac{13}{9}\)-approximation for graphic TSP
• On the integrality gap of the subtour LP for the 1,2-TSP
• Approximating minimum-cost connected \(T\)-joins
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• The traveling salesman problem on cubic and subcubic graphs
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• An LP-based approximation algorithm for the generalized traveling salesman path problem
• The Poisson binomial distribution -- old \& new
• 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)
• Reassembling trees for the traveling salesman
• Nonoblivious 2-opt heuristics for the traveling salesman problem
• Traveling salesman problems in temporal graphs
• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• TSP on cubic and subcubic graphs
• Better s-t-tours by Gao trees
• Constant factor approximation for ATSP with two edge weights (extended abstract)
• The Steiner traveling salesman problem with online edge blockages
• Approximation hardness of graphic TSP on cubic graphs
• An introduction to temporal graphs: an algorithmic perspective
• The minimum spanning tree problem with non-terminal set
• The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
• Spanning closed walks and TSP in 3-connected planar graphs
• Real stability testing
• Random walks in polytopes and negative dependence
• 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
• New inapproximability bounds for TSP
• Towards improving Christofides algorithm for half-integer TSP
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
• Generalized maximum entropy estimation
• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
• TSP tours in cubic graphs: beyond 4/3
• A proof of the Boyd-Carr conjecture
• An introduction to temporal graphs: an algorithmic perspective
• Reducing Path TSP to TSP
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• The temporal explorer who returns to the base
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• On tail triviality of negatively dependent stochastic processes
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Amalgamation of real zero polynomials
• Matroid-based TSP rounding for half-integral solutions
• An improved upper bound for the universal TSP on the grid
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Central limit theorems and the geometry of polynomials
• From trees to polynomials and back again: new capacity bounds with applications to TSP
• Sublinear algorithms for TSP via path covers
• Circulant TSP: vertices of the edge-length polytope and superpolynomial lower bounds
• On polynomial kernels for traveling salesperson problem and its generalizations
• Approximating graphic min-max and minimum cycle/path/tree cover problems
• Circulant TSP special cases: easily-solvable cases and improved approximations
• A lower bound for the max entropy algorithm for TSP
• A lower bound for the max entropy algorithm for TSP
• Improved approximation algorithms for (1,2)-TSP and Max-TSP using path covers in the semi-streaming model
• Quantum speedup for sampling random spanning trees
• Dual charging for half-integral TSP
• Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances
• Parameterized complexity of directed traveling salesman problem

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

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