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

}