Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with n nodes and k clusters, optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4(l)n(3)) and O(2(l)k(l+4)n(3)), respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint H

Translated title of the contributionSolvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours
Original languageRussian
Pages (from-to)280-291
Number of pages12
JournalТруды института математики и механики УрО РАН
Volume23
Issue number3
DOIs
Publication statusPublished - 2017

Keywords

  • Generalized Traveling Salesman Problem (GTSP)
  • polynomially solvable subclass
  • quasi-pyramidal tour
  • pseudopyramidal tour
  • APPROXIMATION ALGORITHMS

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this

@article{3d580d43e9484205aac2d69dd9837d84,
title = "РАЗРЕШИМОСТЬ ОБОБЩЕННОЙ ЗАДАЧИ КОММИВОЯЖЕРА В КЛАССЕ КВАЗИ- И ПСЕВДОПИРАМИДАЛЬНЫХ МАРШРУТОВ",
abstract = "We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with n nodes and k clusters, optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4(l)n(3)) and O(2(l)k(l+4)n(3)), respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint H",
keywords = "Generalized Traveling Salesman Problem (GTSP), polynomially solvable subclass, quasi-pyramidal tour, pseudopyramidal tour, APPROXIMATION ALGORITHMS",
author = "Khachai, {Mikhail Yur'evich} and Neznakhina, {Ekaterina Dmitrievna}",
year = "2017",
doi = "10.21538/0134-4889-2017-23-3-280-291",
language = "Русский",
volume = "23",
pages = "280--291",
journal = "Труды института математики и механики УрО РАН",
issn = "0134-4889",
publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",
number = "3",

}

TY - JOUR

T1 - РАЗРЕШИМОСТЬ ОБОБЩЕННОЙ ЗАДАЧИ КОММИВОЯЖЕРА В КЛАССЕ КВАЗИ- И ПСЕВДОПИРАМИДАЛЬНЫХ МАРШРУТОВ

AU - Khachai, Mikhail Yur'evich

AU - Neznakhina, Ekaterina Dmitrievna

PY - 2017

Y1 - 2017

N2 - We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with n nodes and k clusters, optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4(l)n(3)) and O(2(l)k(l+4)n(3)), respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint H

AB - We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with n nodes and k clusters, optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4(l)n(3)) and O(2(l)k(l+4)n(3)), respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint H

KW - Generalized Traveling Salesman Problem (GTSP)

KW - polynomially solvable subclass

KW - quasi-pyramidal tour

KW - pseudopyramidal tour

KW - APPROXIMATION ALGORITHMS

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000453521100026

UR - https://elibrary.ru/item.asp?id=29938020

U2 - 10.21538/0134-4889-2017-23-3-280-291

DO - 10.21538/0134-4889-2017-23-3-280-291

M3 - Статья

VL - 23

SP - 280

EP - 291

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 3

ER -