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
СостояниеОпубликовано - 22 янв 2020
Событие13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Греция
Продолжительность: 27 мая 201931 мая 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.201931.05.2019

Fingerprint Подробные сведения о темах исследования «Asymptotically Optimal Algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать