An improved upper bound for the universal TSP on the grid

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
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
Coordination mechanisms
Algorithms for the universal and a priori TSP
The Euclidean traveling salesman problem is NP-complete
Universal classes of hash functions
\(\frac{13}{9}\)-approximation for graphic TSP
Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
On the approximability of the traveling salesman problem
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Spacefilling curves and the planar travelling salesman problem
A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
Universal approximations for TSP, Steiner tree, and set cover
Oblivious routing in directed graphs with random demands
Improved lower and upper bounds for universal TSP in planar metrics
Oblivious network design
Improved Lower Bounds for the Universal and a priori TSP
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
Designing Networks with Good Equilibria under Uncertainty
An Improved Upper Bound for the Universal TSP on the Grid
Oblivious routing on node-capacitated and directed graphs
A Randomized Rounding Approach to the Traveling Salesman Problem
Approximating Graphic TSP by Matchings
A Priori Optimization
A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: An improved upper bound for the universal TSP on the grid

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