Abstract
We consider two partial-information generalizations of the metric traveling salesman problem (TSP) in which the task is to produce a total ordering of a given metric space that performs well for a subset of the space that is not known in advance. In the universal TSP, the subset is chosen adversarially, and in the TSP it is chosen probabilistically. Both the universal and TSP have been studied since the mid-80’s, starting with the work of Bartholdi & Platzman and Jaillet, respectively. We prove a lower bound of Ω(logn) for the universal TSP by bounding the competitive ratio of shortest-path metrics on Ramanujan graphs, which improves on the previous best bound of Hajiaghayi, Kleinberg & Leighton, who showed that the competitive ratio of the n ×n grid is \(\Omega(\sqrt[6]{\log n / \log \log n})\). Furthermore, we show that for a large class of combinatorial optimization problems that includes TSP, a bound for the universal problem implies a matching bound on the approximation ratio achievable by deterministic algorithms for the corresponding black-box problem. As a consequence, our lower bound of Ω(logn) for the universal TSP implies a matching lower bound for the black-box TSP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)
Bartholdi, J., Platzman, L.: An o(n logn ) planar traveling salesman heuristic based on spacefilling curves. Operations Research Letters 1(4), 121–125 (1981)
Bartholdi, J., et al.: A minimal technology routing system for meals on wheels. Interfaces 13(3), 1–8 (1983)
Bertsimas, D., Grigni, M.: On the spacefilling curve heuristic for the euclidean traveling salesman problem. Operations Research Letters 8(5), 241–244 (1989)
Bertsimas, D., Jaillet, P., Odoni, A.: On the spacefilling curve heuristic for the euclidean traveling salesman problem. Operations Research Letters 38(6), 1019–1033 (1990)
Bollobás, B.: Modern Graph Theory. Springer, Heidelberg (2001)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485–497 (2004)
Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security preserving amplification of hardness. In: FOCS, pp. 318–326 (1990)
Gorodezky, I., Kleinberg, R., Shmoys, D., Spencer, G.: Improved lower bounds for the universal and a priori TSP. In: TSP (2010) (Preprint), http://people.orie.cornell.edu/~shmoys/GKSS10.pdf
Gupta, A., Hajiaghayi, M., Räcke, H.: Oblivious network design. In: SODA, pp. 970–979 (2006)
Gupta, A., Pál, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: STOC, pp. 417–426 (2004)
Hajiaghayi, M., Kleinberg, R., Leighton, F.: Improved lower and upper bounds for universal tsp in planar metrics. In: SODA, pp. 649–658 (2006)
Jaillet, P.: Probabilistic traveling salesman problems. Technical Report, MIT Operations Research Center, 185 (1985)
Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R.: Universal approximations for tsp, steiner tree, and set cover. In: STOC, pp. 386–395 (2005)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Morgenstern, M.: Existence and explicit constructions of + 1 regular ramanujan graphs for every prime power. J. Comb. Theory, Ser. B 62(1), 44–62 (1994)
Nilli, A.: On the second eigenvalue of a graph. Discrete Mathematics 91(2), 207–210 (1991)
Platzman, L., Bartholdi III, J.: Spacefilling curves and the planar travelling salesman problem. J. ACM 36(4), 719–737 (1989)
Schalekamp, F., Shmoys, D.: Algorithms for the universal and a priori tsp. Oper. Res. Lett. 36(1), 1–3 (2008)
Shmoys, D., Talwar, K.: A constant approximation algorithm for the a priori traveling salesman problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 331–343. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gorodezky, I., Kleinberg, R.D., Shmoys, D.B., Spencer, G. (2010). Improved Lower Bounds for the Universal and a priori TSP. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)