Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

Request-a-Copy directly from author or use local Library Get it For Me service.

Official URL: http://dx.doi.org/10.1007/978-3-319-07890-8_11

Request Changes to record.

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:
DateEvent
2014UNSPECIFIED
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us