Improved Lower Bounds for the Universal and a priori TSP
From MaRDI portal
Publication:3588406
DOI10.1007/978-3-642-15369-3_14zbMath1304.68062OpenAlexW1846028264MaRDI QIDQ3588406
David B. Shmoys, Igor Gorodezky, Gwen Spencer, Robert D. Kleinberg
Publication date: 10 September 2010
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_14
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Load balanced distributed directories ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Approximation algorithms for the a priori traveling repairman ⋮ On the Complexity of Master Problems ⋮ Assouad-Nagata dimension and gap for ordered metric spaces ⋮ Universal Algorithms for Clustering Problems ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ A priori TSP in the Scenario Model ⋮ The A priori traveling repairman problem ⋮ 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
This page was built for publication: Improved Lower Bounds for the Universal and a priori TSP