Improved lower and upper bounds for universal TSP in planar metrics
From MaRDI portal
Publication:3581548
DOI10.1145/1109557.1109628zbMath1192.90172OpenAlexW4243947355MaRDI QIDQ3581548
Leighton Tom, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg
Publication date: 16 August 2010
Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1109557.1109628
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Metric spaces, metrizability (54E35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Approximation algorithms for stochastic combinatorial optimization problems ⋮ Load balanced distributed directories ⋮ Universal Guard Problems ⋮ Universal Algorithms for Clustering Problems ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ A priori TSP in the Scenario Model ⋮ Algorithms for the universal and a priori TSP ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ A priori TSP in the scenario model ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Time-communication impossibility results for distributed transactional memory
