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

Translated title of the contribution: Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours

Research output: Contribution to journalArticle

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