Standard

Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. / Gimadi, Edward Kh; Tsidulko, Oxana.

Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. ed. / Nikolaos F. Matsatsinis; Yannis Marinakis; Panos Pardalos. Springer Gabler, 2020. p. 201-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS).

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

Harvard

Gimadi, EK & Tsidulko, O 2020, Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. in NF Matsatsinis, Y Marinakis & P Pardalos (eds), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11968 LNCS, Springer Gabler, pp. 201-207, 13th International Conference on Learning and Intelligent Optimization, LION 13, Chania, Greece, 27.05.2019. https://doi.org/10.1007/978-3-030-38629-0_16

APA

Gimadi, E. K., & Tsidulko, O. (2020). Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. In N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Eds.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (pp. 201-207). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_16

Vancouver

Gimadi EK, Tsidulko O. Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. In Matsatsinis NF, Marinakis Y, Pardalos P, editors, Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Springer Gabler. 2020. p. 201-207. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38629-0_16

Author

Gimadi, Edward Kh ; Tsidulko, Oxana. / Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. editor / Nikolaos F. Matsatsinis ; Yannis Marinakis ; Panos Pardalos. Springer Gabler, 2020. pp. 201-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{16706dacbbcc4ea0b75eb57870657a7c,
title = "Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs",
abstract = "The Prize-Collecting Traveling Salesman Problem is a class of generalizations of the classic Traveling Salesman Problem (TSP) where it is not necessary to visit all the vertices. Given the edge costs and a certain profit associated with each vertex, the goal is to find a route which satisfies maximum collected profit and minimum traveling costs constraints. We show polynomial-time approximation algorithms for two variants of the problem and establish conditions under which the presented algorithms are asymptotically optimal on random inputs.",
keywords = "Asymptotically optimal algorithm, NP-hard problem, Prize-collecting TSP, Random inputs",
author = "Gimadi, {Edward Kh} and Oxana Tsidulko",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",
year = "2020",
month = jan,
day = "22",
doi = "10.1007/978-3-030-38629-0_16",
language = "English",
isbn = "9783030386283",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "201--207",
editor = "Matsatsinis, {Nikolaos F.} and Yannis Marinakis and Panos Pardalos",
booktitle = "Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs

AU - Gimadi, Edward Kh

AU - Tsidulko, Oxana

N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/22

Y1 - 2020/1/22

N2 - The Prize-Collecting Traveling Salesman Problem is a class of generalizations of the classic Traveling Salesman Problem (TSP) where it is not necessary to visit all the vertices. Given the edge costs and a certain profit associated with each vertex, the goal is to find a route which satisfies maximum collected profit and minimum traveling costs constraints. We show polynomial-time approximation algorithms for two variants of the problem and establish conditions under which the presented algorithms are asymptotically optimal on random inputs.

AB - The Prize-Collecting Traveling Salesman Problem is a class of generalizations of the classic Traveling Salesman Problem (TSP) where it is not necessary to visit all the vertices. Given the edge costs and a certain profit associated with each vertex, the goal is to find a route which satisfies maximum collected profit and minimum traveling costs constraints. We show polynomial-time approximation algorithms for two variants of the problem and establish conditions under which the presented algorithms are asymptotically optimal on random inputs.

KW - Asymptotically optimal algorithm

KW - NP-hard problem

KW - Prize-collecting TSP

KW - Random inputs

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

U2 - 10.1007/978-3-030-38629-0_16

DO - 10.1007/978-3-030-38629-0_16

M3 - Conference contribution

AN - SCOPUS:85082389095

SN - 9783030386283

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

SP - 201

EP - 207

BT - Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers

A2 - Matsatsinis, Nikolaos F.

A2 - Marinakis, Yannis

A2 - Pardalos, Panos

PB - Springer Gabler

T2 - 13th International Conference on Learning and Intelligent Optimization, LION 13

Y2 - 27 May 2019 through 31 May 2019

ER -

ID: 23892780