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

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

Journal

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Output data

Year: 2020, Volume: 11968, Pages: 201-207 Pages count : 7 DOI: 10.1007/978-3-030-38629-0_16

Tags

Asymptotically optimal algorithm; NP-hard problem; Prize-collecting TSP; Random inputs

Authors

Gimadi E.K. ^1,2 , Tsidulko O. ^1,2

Affiliations

1	Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
2	Department of Mechanics and Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation

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. © 2020, Springer Nature Switzerland AG.

Gimadi E.K. , Tsidulko O.
Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs
Lecture Notes in Computer Science. 2020. V.11968. P.201-207. DOI: 10.1007/978-3-030-38629-0_16 WOS Scopus OpenAlex

Web of science:	WOS:000656458800016
Scopus:	2-s2.0-85082389095
OpenAlex:	W3001918660

DB	Citing
Scopus	2
Web of science	2
OpenAlex	2