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

Resultado de la investigación: Articlerevisión exhaustiva

Resumen

Условие обобщенной задачи коммивояжера (Generalized Traveling Salesman Problem, GTSP) задается взвешенным графом $G=(V,E,w)$ и разбиением множества его вершин на $k$ дизъюнктных кластеров $V=V_1\cup\ldots\cup V_k$. Требуется построить цикл минимального веса, посещающий в точности одну вершину из каждого кластера. Мы рассматриваем геометрическую постановку задачи (именуемую в работе EGTSP-$k$-GC), в которой вершины графа являются точками на плоскости, весовая функция задается евклидовыми расстояниями между ними, а разбиение на кластеры определяется неявно с помощью регулярной целочисленной сетки с шагом 1. Произвольным образом разрешая неоднозначность, в рассматриваемой нами постановке назовем кластером подмножество вершин, принадлежащих одной ячейке данной сетки. Даже в этом частном случае обобщенная задача коммивояжера остается труднорешаемой, являясь естественным обобщением классической евклидовой задачи коммивояжера на плоскости. Недавно для данной задачи был построен $(1.5 + 8\sqrt2 + \varepsilon)$-приближенный алгоритм с трудоемкостью, зависящей полиномиально как от числа вершин $n$, так и от количества кластеров $k$. Мы предлагаем три приближенные схемы для этой задачи. При произвольном фиксированном $k$ все схемы являются полиномиальными (PTAS), причем трудоемкость первых двух линейна по числу вершин. Более того, первые две схемы остаются полиномиальными при $k=O(\log n)$, а последняя схема сохраняет свойство полиномиальности при $k=n-O(\log n)$.
Título traducido de la contribuciónApproximation schemes for the generalized TSP
Idioma originalRussian
Páginas (desde-hasta)283-292
Número de páginas10
PublicaciónТруды института математики и механики УрО РАН
Volumen22
N.º3
DOI
EstadoPublished - 2016

Level of Research Output

  • VAK List

Citar esto