Abstract
What is the most efficient way of lacing a shoe? Mathematically speaking, this question concerns the structure of certain special cases of the bipartite travelling salesman problem (BTSP).
We show that techniques developed for the analysis of the (standard) TSP may be applied successfully to characterize well-solvable cases of the BTSP and the shoelace problem. In particular, we present a polynomial time algorithm that decides whether there exists a renumbering of the cities such that the resulting distance matrix carries a benevolent combinatorial structure that allows one to write down the optimal solution without further analysis of input data. Our results generalize previously published well-solvable cases of the shoelace problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Anily, S., Hassin, R.: The swapping problem. Networks 22, 11–18 (1992)
Atallah, M.J., Kosaraju, S.R.: Efficient solutions to some transportation problems with applications to minimizing robot arm travel. SIAM Journal on Computing 17, 419–433 (1988)
Baltz, A.: Algorithmic and probabilistic aspects of the bipartite travelling salesman problem. PhD Thesis. University of Kiel, Germany (2001)
Baltz, A., Srivastav, A.: Approximation algorithms for the Euclidean bipartite TSP. Operations Research Letters 33, 403–410 (2005)
Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the TSP: A survey. SIAM Review 40, 496–546 (1998)
Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Applied Mathematics 70, 91–161 (1996)
Burkard, R.E., Deineko, V.: On the travelling salesman problem with a relaxed Monge matrix. Information Processing Letters 67, 231–237 (1998)
Chalasani, P., Motwani, R., Rao, A.: Algorithms for robot grasp and delivery. In: Proceedings of the 2nd International Workshop on Algorithmic Foundations of Robotics, Toulouse, France, pp. 347–362 (1996)
Deineko, V., Woeginger, G.J.: The maximum travelling salesman problem on symmetric Demidenko matrices. Discrete Applied Mathematics 99, 413–425 (2000)
Demidenko, V.M.: A special case of travelling salesman problems. Izvestiya Akademii Nauk BSSR, Seriya Fiziko-Matematicheskikh Nauk 5, 28–32 (1976) (in Russian)
Frank, A., Korte, B., Triesch, E., Vygen, J.: On the bipartite travelling salesman problem.Technical Report No. 98866-OR. Research Institute for Discrete Mathematics, University of Bonn, Germany (1998)
Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. In: [16], ch. 4, pp. 87–143 (1985)
Halton, J.H.: The shoelace problem. The Mathematical Intelligencer 17, 36–41 (1995)
Kalmanson, K.: Edge-convex circuits and the travelling salesman problem. Canadian Journal of Mathematics 27, 1000–1010 (1975)
Leipälä, T., Nevalainen, O.: Optimization of the movements of a component placement machine. European Journal of Operational Research 38, 167–177 (1989)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem. Wiley, Chichester (1985)
Michel, C., Schroeter, H., Srivastav, A.: Approximation algorithms for pick-and-place robots. Annals of Operations Research 107, 321–338 (2001)
Misiurewicz, M.: Lacing irregular shoes. The Mathematical Intelligencer 18, 32–34 (1996)
Polster, B.: Lacing irregular shoes. Nature 420, 476 (2002)
Polster, B.: The shoelace book: a mathematical guide to the best (and worst) ways to lace your shoes. American Mathematical Society (2006)
Supnick, F.: Extreme Hamiltonian lines. Annals of Mathematics 66, 179–201 (1957)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Deineko, V.G., Woeginger, G.J. (2014). Another Look at the Shoelace TSP: The Case of Very Old Shoes. In: Ferro, A., Luccio, F., Widmayer, P. (eds) Fun with Algorithms. FUN 2014. Lecture Notes in Computer Science, vol 8496. Springer, Cham. https://doi.org/10.1007/978-3-319-07890-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-07890-8_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07889-2
Online ISBN: 978-3-319-07890-8
eBook Packages: Computer ScienceComputer Science (R0)