The Library
Another look at the shoelace TSP : the case of very old shoes
Tools
Tools
Tools
Deineko, Vladimir G. and Woeginger, Gerhard J. (2014) Another look at the shoelace TSP : the case of very old shoes. In: Ferro , Alfredo and Luccio , Fabrizio , (eds.) Proceedings of 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Lecture Notes in Computer Science, Volume 8496 . Berlin Heidelberg: Springer, pp. 125-126. ISBN 9783319078892
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/978-3-319-07890-8_11
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
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Social Sciences > Warwick Business School | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Journal or Publication Title: | Fun with Algorithms | ||||
| Publisher: | Springer | ||||
| Place of Publication: | Berlin Heidelberg | ||||
| ISBN: | 9783319078892 | ||||
| Book Title: | Proceedings of 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014 | ||||
| Editor: | Ferro , Alfredo and Luccio , Fabrizio | ||||
| Official Date: | 2014 | ||||
| Dates: |
|
||||
| Volume: | Volume 8496 | ||||
| Page Range: | pp. 125-126 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 7th International Conference, Fun with Algorithms (FUN) 2014 | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Sicily, Italy | ||||
| Date(s) of Event: | 1-3 Jul 2014 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
