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

Edward Kh Gimadi; Oxana Tsidulko

doi:10.1007/978-3-030-38629-0_16

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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

Аннотация

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.

Язык оригинала	английский
Название основной публикации	Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
Редакторы	Nikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
Издатель	Springer Gabler
Страницы	201-207
Число страниц	7
ISBN (печатное издание)	9783030386283
DOI	https://doi.org/10.1007/978-3-030-38629-0_16
Состояние	Опубликовано - 22 янв 2020
Событие	13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Греция Продолжительность: 27 мая 2019 → 31 мая 2019

Серия публикаций

Название	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том	11968 LNCS
ISSN (печатное издание)	0302-9743
ISSN (электронное издание)	1611-3349

Конференция

Конференция	13th International Conference on Learning and Intelligent Optimization, LION 13
Страна	Греция
Город	Chania
Период	27.05.2019 → 31.05.2019

Fingerprint

Цитировать

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

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. редактор / Nikolaos F. Matsatsinis ; Yannis Marinakis ; Panos Pardalos. Springer Gabler, 2020. стр. 201-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

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",

note = "13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",

}

Gimadi, EK & Tsidulko, O 2020, Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs. в NF Matsatsinis, Y Marinakis & P Pardalos (ред.), 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), том. 11968 LNCS, Springer Gabler, стр. 201-207, 13th International Conference on Learning and Intelligent Optimization, LION 13, Chania, Греция, 27.05.2019. https://doi.org/10.1007/978-3-030-38629-0_16

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. ред. / Nikolaos F. Matsatsinis; Yannis Marinakis; Panos Pardalos. Springer Gabler, 2020. стр. 201-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11968 LNCS).

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

TY - GEN

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

AU - Gimadi, Edward Kh

AU - Tsidulko, Oxana

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 -

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

Доступ к документу

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

Link to publication in Scopus