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, 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, 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. 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. 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, 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",
pages = "283--293",
booktitle = "Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers",
address = "United States",

}

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

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