Приближенные схемы для обобщенной задачи коммивояжера

Условие обобщенной задачи коммивояжера (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)$.