In this paper, we introduce notions of l-quasi-pyramidal and l-pseudopyramidal tours extending the classic notion of pyramidal tour to the case of Generalized Traveling Salesman Problem (GTSP). We show that, for the instance of GTSP on n cities and k clusters with arbitrary weights, optimal l-quasi-pyramidal and l-pseudo-pyramidal tours can be found in time O(4ln3) and O(2lkl+4n3), respectively. Consequently, we show, that, in the most general setting, GTSP belongs to FPT for parametrizations induced by these special kinds of tours. Also, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of optimal l-quasi-pyramidal tour (for some fixed value of l) is proved.
Algorithmic issues of finding optimal restricted tours, for several kinds of restrictions, e.g. precedence
constraints, are also actively investigated
Contribution of this paper is two-fold. At first, we introduce (in Section 2) notions of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tour and results of [Oda & Ota, 2001] to the case of Generalized Traveling Salesman Problem (GTSP). We show that optimal l-quasi-pyramidal and l-pseudopyramidal tours can be found in time O(4ln3) and O(2lkl+4n3), respectively. At second, we describe (in Section 3) a non-trivial polynomially solvable subclass of GTSP, for which the existence of optimal l-quasi-pyramidal tour (for some fixed l) is proved. 2
We proceed with the common setting of the Generalized Traveling Salesman Problem (GTSP). Instance of the GTSP is defined by complete edge-weighted graph G = (V; E; w) with weighting function w : E → R+, and by a given partition V1 ∪ : : : ∪ Vk = V of the nodeset V = V (G) of graph G. Feasible solutions are cyclic tours vi1 ; : : : ; vik visiting each cluster Vi once. Hereinafter, we call such routes Clustered Hamiltonian tours or CH-tours. The problem is to find a CH-tour of the minimum weight1.
In this section, we extend the well-known notion of a pyramidal tour to the case of partial orders defined implicitly by the orderings of clusters. Indeed, linear ordered finite set (V1; : : : ; Vk) of clusters induces a partial order on the nodeset V of the graph G as follows, for any u ∈ Vi and v ∈ Vj , u ≺ v if i < j. De nition 1 Let be a CH-tour v1; vi1 ; : : : ; vir ; vk; vjk−r−2 ; : : : ; vj1 such that vt ∈ Vt for any t. We call l-quasi-pyramidal tour, if ip − iq ≤ l and jp′ − jq′ ≤ l for any 1 ≤ p < q ≤ r and 1 ≤ p′ < q′ ≤ k − r − 2. an
The following theorems extend the results proposed in [Oda & Ota, 2001] for the classic TSP. Theorem 1 For any weighting function w : E → R+, a minimum cost l-quasi-pyramidal CH-tour can be found in time of O(4ln3).
Remark 1 Evidently, result of Theorem 1 can be considered in the context of the parameterized complexity. Actually, Theorem 1 claims that, in the most general setting, GTSP is xed-parameter tractable with respect to parametrization induced by quasi-pyramidal tours.
In Section 3, we describe a subclass of geometric GTSP, each whose instance has l-quasi-pyramidal optimal tours for some fixed l. Nevertheless, this class seems to be very specific, and the scheme proposed can hardly be extended to more general settings. To overcome this gap, we propose a more common notion of pyramidal-like tours. We call them pseudo-pyramidal.
De nition 2 Let be a CH-tour v1; vi1 ; : : : ; vir ; vk; vjk−r−2 ; : : : ; vj1 such that vt ∈ Vt for any t. We call l-pseudo-pyramidal tour, if ip − ip+1 ≤ l and jq − jq+1 ≤ l for any 1 ≤ p ≤ r − 1 and 1 ≤ q ≤ k − r − 1. an It easy to verify that any l-quasi-pyramidal tour is an l-pseudo-pyramidal as well.
1In this paper, we restrict ourselves to the case of undirected graphs. Although, the similar argument can be provided to the case of digraphs and asymmetric weighting functions w. Theorem 2 For any weighting function w : E → R+, a minimum cost l-pseudo-pyramidal CH-tour can be found in time of O(2lkl+4n3).
Remark 2 As for Theorem 1, Theorem 2 states that, for any weighting function, GTSP belongs to FPT with respect to parameters k and l. Also, since O(2l(log n)l+4n3) = 2O(l2) · O(n4), the problem has FPT algorithms with respect to parameter l only any time when k = O(log n).
For the brevity, we skip proofs of Theorems 1 and 2, which will be come in forthcoming paper. 3
In this section, we describe polynomially solvable subclass of Generalized Traveling Salesman Problem on Grid Clusters, GTSP-GC for short. In this special case of the GTSP, an undirected edge-weighted graph G = (V; E; w) is given where the set of vertices V correspond to a set of points in the planar rectangular grid. Every nonempty 1 × 1 cell of the grid forms a cluster. The weighting function is induced by distances between the appropriate points with respect to some metric. To put it simple, we consider Euclidean distances, but the similar results can be easily obtained for some other metrics, e.g. for l1. In Fig. 1, we present an instance of the Euclidean GTSP-GC with 6 clusters.
It is known that for two special cases of the problem, when the number k of clusters is O(logn) or n − O(logn), polynomial time approximation schemes (PTAS) were proposed [Khachay & Neznakhina, 2016b]. Meanwhile, the question of systematic description of polynomial time solvable subclasses of GTSP-GC, which is closely related to complexity analysis of Hamiltonian cycle problem on grid graphs, is still far from its complete answer.
Let H and W be height and width (number of rows and columns) of the given grid, respectively. We consider a special case of the GTSP-GC, for which one of these parameters, say H does not exceed 2 (while another one is unbounded). We call this case GTSP-GC(H2). We show that any instance of GTSP-GC(H2) has an optimal l-quasi-pyramidal CH-tour for some l independent on n. Therefore, this subclass of GTSP-GC is polynomially solvable due to Theorem 1.
Our argument is based on the introduced Tour straightening transformation (Algorithm 1), which is closely related to the well-known class of local search heuristics. To describe the transformation, assign to columns of the grid defining the given instance of GTSP-GC(H2), integer numbers 1; 2; : : : ; W (from the left to the right). Consider an arbitrary CH-tour . Assigning to each node vi of the number ci of the column it belongs, obtain a sequence of column numbers presented in the order induced by the tour . Without loss of generality, assume that has the form
1 = c1; c2; : : : ; cr = W; cr+1; : : : ; cs = 1 for some appropriate numbers r and s.
Suppose, for some integer number t, whose value will be specified later, there exist indexes 1 ≤ p < q ≤ r; r + 1 ≤ p′ < q′ ≤ s; such that such that cp − cq ≥ t − 1; or cq′ − cp′ ≥ t − 1: (1) (2) (3) In this case, we say that the tour has t-zigzag (Fig. 2). Obviously, any l-quasi-pyramidal tour contains no t-zigzags, for any t ≥ l. Algorithm 1 replaces all segments of the tour having t-zigzags with subtours of the special kind (see. Fig. 3). Algorithm 1 Tour straightening transformation Outer Parameter: t.
Input: an instance of GTSP-GC(H2) and a CH-tour .
Output: a CH-tour ′ without t-zigzags. Meanwhile, the weight of their replacement in Step 7 at any iteration of Algorithm 1 is at most 2t + 2F (Y; [0; 2]), where F (Y; S) is an optimum value of 2-medians clustering objective function for a sample Y taken from a line segment S.
To estimate an upper bound for F (Y; S) we need the following technical lemma, which can be easily proved by recurrent variable elimination method of linear programming. Lemma 1 For any sample = (p1; : : : ; pn), pi ∈ [0; 1] there exist numbers m1 and m2 ∈ [0; 1] such that
n F ( ; [0; 1]) = ∑ min{|pi − m1|; |pi − m2|} ≤ n=6: i=1 (4)
Getting back to discussion of Algorithm 1, we obtain from Lemma 1 that F (Y; [0; 2]) ≤ 2 · 1=6(2t + 4). Therefore, at any iteration of Algorithm 1, the tour ′ becomes cheeper if 2t + 4t=3 + 8=3 ≤ 4t − 4, i.e. t ≥ 10.
Further, let cells of the grid be ordered as in Fig. 4 (i.e., top-down and left-right). For t = 10, any CH-tour of the given GTSP-GC(H2) instance can be transformed to l-quasi-pyramidal CH-tour for l = 20 without increasing its weight. Hence, we are proved the following theorem.
Theorem 3 Any instance of GTSP-GC(H2) has an optimal 20-quasi-pyramidal CH-tour. As a consequence of Theorem 1 and Theorem 3, we obtain that GTSP-GC(H2) can be solved to optimality in time O(n3). 4
In this paper, a new notion of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tour is introduced. We show that, similar to the case of pyramidal tours and TSP, an optimal lquasi-pyramidal tour for the Generalized Traveling Salesman Problem can be found efficiently (for an arbitrary weighting function). Also, we describe a non-trivial polynomially solvable geometric special case of GTSP. Each instance of the problem in question has an l-quasi-pyramidal tour as an optimal solution. Actually, an instance of this problem is defined by unit 2-row rectangular grid on the Euclidean plane. Although, the the trick with 2-medians can not be applied straightforward even to the case h = 3, we believe that we can prove soon the existence of optimal l-pseudo-pyramidal tours for the case of GTSP-GC(Hh) defined by a grid of an arbitrary fixed height h.
Acknowledgements This research was supported by Russian Science Foundation, project no. 14-11-00109.