Another look at the shoelace TSP : the case of very old shoes

V.G. Deineko; G.J. Woeginger

doi:10.1007/978-3-319-07890-8_11

Another look at the shoelace TSP : the case of very old shoes

V.G. Deineko, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

1 Downloads (Pure)

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. Keywords: Bipartite travelling salesman problem; shoelace problem; polynomially solvable case; relaxed Monge matrix; pick-and-place robot

Original language	English
Title of host publication	Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings)
Editors	A. Ferro, F. Luccio, P. Widmayer
Place of Publication	Berlin
Publisher	Springer
Pages	125-136
ISBN (Print)	978-3-319-07889-2
DOIs	https://doi.org/10.1007/978-3-319-07890-8_11
Publication status	Published - 2014
Event	7th International Conference on Fun with Algorithms (FUN 2014) - Lipari Island, Sicily, Italy Duration: 1 Jul 2014 → 3 Jul 2014 Conference number: 7

Publication series

Name	Lecture Notes in Computer Science
Volume	8496
ISSN (Print)	0302-9743

Conference

Conference	7th International Conference on Fun with Algorithms (FUN 2014)
Abbreviated title	FUN 2014
Country/Territory	Italy
City	Lipari Island, Sicily
Period	1/07/14 → 3/07/14

Access to Document

10.1007/978-3-319-07890-8_11

Cite this

Deineko, V. G., & Woeginger, G. J. (2014). Another look at the shoelace TSP : the case of very old shoes. In A. Ferro, F. Luccio, & P. Widmayer (Eds.), Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings) (pp. 125-136). (Lecture Notes in Computer Science; Vol. 8496). Springer. https://doi.org/10.1007/978-3-319-07890-8_11

@inproceedings{0622e34e3bc94369af042470812d2aac,

title = "Another look at the shoelace TSP : the case of very old shoes",

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. Keywords: Bipartite travelling salesman problem; shoelace problem; polynomially solvable case; relaxed Monge matrix; pick-and-place robot",

author = "V.G. Deineko and G.J. Woeginger",

year = "2014",

doi = "10.1007/978-3-319-07890-8_11",

language = "English",

isbn = "978-3-319-07889-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "125--136",

editor = "A. Ferro and F. Luccio and P. Widmayer",

booktitle = "Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings)",

address = "Germany",

note = "7th International Conference on Fun with Algorithms (FUN 2014), FUN 2014 ; Conference date: 01-07-2014 Through 03-07-2014",

}

Deineko, VG & Woeginger, GJ 2014, Another look at the shoelace TSP : the case of very old shoes. in A Ferro, F Luccio & P Widmayer (eds), Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings). Lecture Notes in Computer Science, vol. 8496, Springer, Berlin, pp. 125-136, 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Sicily, Italy, 1/07/14. https://doi.org/10.1007/978-3-319-07890-8_11

Another look at the shoelace TSP : the case of very old shoes. / Deineko, V.G.; Woeginger, G.J.
Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings). ed. / A. Ferro; F. Luccio; P. Widmayer. Berlin: Springer, 2014. p. 125-136 (Lecture Notes in Computer Science; Vol. 8496).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Another look at the shoelace TSP : the case of very old shoes

AU - Deineko, V.G.

AU - Woeginger, G.J.

N1 - Conference code: 7

PY - 2014

Y1 - 2014

N2 - 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. Keywords: Bipartite travelling salesman problem; shoelace problem; polynomially solvable case; relaxed Monge matrix; pick-and-place robot

AB - 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. Keywords: Bipartite travelling salesman problem; shoelace problem; polynomially solvable case; relaxed Monge matrix; pick-and-place robot

U2 - 10.1007/978-3-319-07890-8_11

DO - 10.1007/978-3-319-07890-8_11

M3 - Conference contribution

SN - 978-3-319-07889-2

T3 - Lecture Notes in Computer Science

SP - 125

EP - 136

BT - Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings)

A2 - Ferro, A.

A2 - Luccio, F.

A2 - Widmayer, P.

PB - Springer

CY - Berlin

T2 - 7th International Conference on Fun with Algorithms (FUN 2014)

Y2 - 1 July 2014 through 3 July 2014

ER -

Another look at the shoelace TSP : the case of very old shoes

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this