Improved Lower Bounds for the Universal and a priori TSP
From MaRDI portal
Publication:3588406
DOI10.1007/978-3-642-15369-3_14zbMath1304.68062MaRDI 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
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Designing Networks with Good Equilibria under Uncertainty, The A priori traveling repairman problem, A priori TSP in the scenario model, Approximation algorithms for the a priori traveling repairman, On the Complexity of Master Problems, A priori TSP in the Scenario Model, Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs, Routing Under Uncertainty: The a priori Traveling Repairman Problem