Standard

On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. / Gimadi, Edward Kh; Tsidulko, Oxana Yu.

Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. p. 283-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS).

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

Harvard

Gimadi, EK & Tsidulko, OY 2018, On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. in Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11179 LNCS, Springer-Verlag GmbH and Co. KG, pp. 283-293, 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018, Moscow, Russian Federation, 05.07.2018. https://doi.org/10.1007/978-3-030-11027-7_27

APA

Gimadi, E. K., & Tsidulko, O. Y. (2018). On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. In Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (pp. 283-293). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11179 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-11027-7_27

Vancouver

Gimadi EK, Tsidulko OY. On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. In Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 283-293. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-11027-7_27

Author

Gimadi, Edward Kh ; Tsidulko, Oxana Yu. / On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem. Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. pp. 283-293 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{0502a9aa7d0f452896336078a1b10b93,
title = "On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem",
abstract = "The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptotically optimal algorithm for the Euclidean maximum TSP with running-time O(n3), that uses a maximum weight cycle cover of the initial graph as a foundation for constructing the TSP solution. We also prove a number of structural results for the optima of some maximization problems in normed spaces, which follow from the algorithm.",
keywords = "Asymptotically optimal algorithm, Cycle cover, Euclidean space, Maximum traveling salesman problem, Metric space, Normed space",
author = "Gimadi, {Edward Kh} and Tsidulko, {Oxana Yu}",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 ; Conference date: 05-07-2018 Through 07-07-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-030-11027-7_27",
language = "English",
isbn = "9783030110260",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "283--293",
booktitle = "Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - On modification of an asymptotically optimal algorithm for the maximum Euclidean traveling salesman problem

AU - Gimadi, Edward Kh

AU - Tsidulko, Oxana Yu

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2018.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptotically optimal algorithm for the Euclidean maximum TSP with running-time O(n3), that uses a maximum weight cycle cover of the initial graph as a foundation for constructing the TSP solution. We also prove a number of structural results for the optima of some maximization problems in normed spaces, which follow from the algorithm.

AB - The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptotically optimal algorithm for the Euclidean maximum TSP with running-time O(n3), that uses a maximum weight cycle cover of the initial graph as a foundation for constructing the TSP solution. We also prove a number of structural results for the optima of some maximization problems in normed spaces, which follow from the algorithm.

KW - Asymptotically optimal algorithm

KW - Cycle cover

KW - Euclidean space

KW - Maximum traveling salesman problem

KW - Metric space

KW - Normed space

UR - http://www.scopus.com/inward/record.url?scp=85059937588&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-11027-7_27

DO - 10.1007/978-3-030-11027-7_27

M3 - Conference contribution

AN - SCOPUS:85059937588

SN - 9783030110260

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 283

EP - 293

BT - Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers

PB - Springer-Verlag GmbH and Co. KG

T2 - 7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018

Y2 - 5 July 2018 through 7 July 2018

ER -

ID: 18129369