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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

2 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

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

Originele taal-2	Engels
Titel	Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings)
Redacteuren	A. Ferro, F. Luccio, P. Widmayer
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	125-136
ISBN van geprinte versie	978-3-319-07889-2
DOI's	https://doi.org/10.1007/978-3-319-07890-8_11
Status	Gepubliceerd - 2014
Evenement	7th International Conference on Fun with Algorithms (FUN 2014) - Lipari Island, Sicily, Italië Duur: 1 jul. 2014 → 3 jul. 2014 Congresnummer: 7

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	8496
ISSN van geprinte versie	0302-9743

Congres

Congres	7th International Conference on Fun with Algorithms (FUN 2014)
Verkorte titel	FUN 2014
Land/Regio	Italië
Stad	Lipari Island, Sicily
Periode	1/07/14 → 3/07/14
Ander	7th International Conference on Fun with Algorithms

Toegang tot document

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

Citeer dit

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 (editors), Fun with Algorithms (7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings) (blz. 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 (uitgave), 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, blz. 125-136, 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Sicily, Italië, 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). uitgave / A. Ferro; F. Luccio; P. Widmayer. Berlin: Springer, 2014. blz. 125-136 (Lecture Notes in Computer Science; Vol. 8496).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit