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