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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.

Original languageEnglish
Title of host publicationLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
EditorsNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
PublisherSpringer Gabler
Pages201-207
Number of pages7
ISBN (Print)9783030386283
DOIs
Publication statusPublished - 22 Jan 2020
Event13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Greece
Duration: 27 May 201931 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11968 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Learning and Intelligent Optimization, LION 13
CountryGreece
CityChania
Period27.05.201931.05.2019

    Fingerprint

Keywords

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

Cite this

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