=Paper=
{{Paper
|id=Vol-1987/paper46
|storemode=property
|title=Quasi- and Pseudo-pyramidal Tours for Generalized Traveling Salesman Problem
|pdfUrl=https://ceur-ws.org/Vol-1987/paper46.pdf
|volume=Vol-1987
|authors=Michael Khachay,Katherine Neznakhina
}}
==Quasi- and Pseudo-pyramidal Tours for Generalized Traveling Salesman Problem==
https://ceur-ws.org/Vol-1987/paper46.pdf
Quasi- and Pseudo-pyramidal Tours
for Generalized Traveling Salesman Problem
Michael Khachay
Krasovsky Institute of Mathematics and Mechanics,
Ural Federal University, Ekaterinburg, Russia
Omsk State Technical University, Omsk, Russia
mkhachay@imm.uran.ru
Katherine Neznakhina
Krasovsky Institute of Mathematics and Mechanics,
Ural Federal University, Ekaterinburg, Russia
eneznakhina@yandex.ru
Abstract
In this paper, we introduce notions of l-quasi-pyramidal and l-pseudo-
pyramidal 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(4l n3 ) and O(2l k l+4 n3 ), 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.
1 Introduction
The Traveling Salesman Problem (TSP) is the famous combinatorial optimization problem having many
valuable applications in operations research and attracting interest of scientists for decades (see, e.g.
[Gutin & Punnen, 2007, Pardalos et al., 2013]).
It is known that TSP is strongly NP-hard and hardly approximable in its general setting
[Sahni & Gonzales, 1976]. At the same time, the problem remains intractable in metric and Euclidean
settings. TSP can be approximated well in these cases admitting fixed-ratio algorithms for an ar-
bitrary metric [Christofides, 1975] and Polynomial Time Approximation Schemes (PTAS) for Euclidean
spaces of any fixed dimension [Arora, 1998]. Many generalizations of TSP, e.g. Cycle Cover Problem
[Gimadi & Rykov, 2016, Khachay & Neznakhina, 2016a, Khachai & Neznakhina, 2015], Peripatetic Salesman
Problem [Baburin et al., 2009, Gimadi et al., 2014], have the similar approximation behaviour.
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
316
Algorithmic issues of finding optimal restricted tours, for several kinds of restrictions, e.g. precedence con-
straints, are also actively investigated (see.,e.g. [Balas, 1999, Balas & Simonetti, 2001, Chentsov et al., 2016]).
Among others, the restriction of TSP to considering so called pyramidal tours (see, e.g. [Burkard et al., 1998])
seems to be especially popular. The pyramidal tour respects the initial order {1, . . . , n} defined on the nodeset
of a given graph and has the form
1 = vi1 , vi2 , . . . , vir = n, vir+1 , . . . , vin ,
where vij < vij+1 for any j ∈ {1, . . . , r − 1} and vij > vij+1 for any j ∈ {r + 1, . . . , n − 1}. It is widely
known [Klyaus, 1976] that an optimal pyramidal tour can be found in time of O(n2 ) for any weighting function.
Recently it was shown [Berg et al., 2016] that, for the Euclidean setting, optimal pyramidal tour can be found in
O(n log2 n) time. In papers [Enomoto et al., 1998, Oda & Ota, 2001], several generalizations of pyramidal tours,
for which an optimal tour also can be found efficiently, were introduced. Despite their fame, pyramidal tours
have one shortcoming. Known settings of TSP and its generalizations, for which existence of optimal pyramidal
tours is proven [Burkard & Deineko, 1998, Baki & Kabadi, 1999, Baki, 2006], remain very rare so far. Actually,
they are mostly exhausted with settings satisfying the well known sufficient conditions by Demidenko and van
der Veen (see, e.g. [Gutin & Punnen, 2007]).
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-pseudo-
pyramidal tours can be found in time O(4l n3 ) and O(2l k l+4 n3 ), 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 Quasi- and Pseudo-pyramidal Tours
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.
Definition 1 Let τ be a CH-tour v1 , vi1 , . . . , vir , vk , vjk−r−2 , . . . , vj1 such that vt ∈ Vt for any t. We call τ an
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.
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(4l n3 ).
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 fixed-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.
Definition 2 Let τ be a CH-tour v1 , vi1 , . . . , vir , vk , vjk−r−2 , . . . , vj1 such that vt ∈ Vt for any t. We call τ an
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.
It easy to verify that any l-quasi-pyramidal tour is an l-pseudo-pyramidal as well.
1 In 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.
317
Theorem 2 For any weighting function w : E → R+ , a minimum cost l-pseudo-pyramidal CH-tour can be found
in time of O(2l k l+4 n3 ).
Remark 2 As for Theorem 1, Theorem 2 states that, for any weighting function, GTSP belongs to FPT with
2
respect to parameters k and l. Also, since O(2l (log n)l+4 n3 ) = 2O(l ) · 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 Polynomial Time Solvable Subclass of GTSP on Grid Clusters
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.
Figure 1: An instance of the Euclidean GTSP-GC and its optimal solution
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 (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, such that cp − cq ≥ t − 1, or (2)
r + 1 ≤ p′ < q ′ ≤ s, such that cq′ − cp′ ≥ t − 1. (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).
318
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.
1: set τ ′ := τ
2: while τ ′ has t-zigzag do
3: assume that equation (2) is valid (without loss of generality, we assume that cp − cq = t − 1), the case of (3) can be treated
similarly;
4: let C be the set of columns with numbers cq , . . . , cp (see Fig. 2);
5: let Y = (y1 , . . . , y2t+4 ) be the ordinate sequence of nodes visited by τ in C augmented by ordinates of left and right crossing
points;
6: find an optimal 2-medians clustering for Y with medians m1 and m2 ;
7: replace segments of the tour τ ′ belonging to C by horizontal lines at height m1 and m2 connected to all points mentioned in
Step 5 by line segments (Fig. 3)
8: end while
9: output the CH-tour τ ′ .
Figure 2: Segment of τ with t-zigzag Figure 3: Replacing t-zigzag with tour segments
of special kind
Figure 4: Cluster ordering
To specify the value of t, notice that the weight of eliminated segments of τ has an evident lower bound
t + 2(t − 1) + t − 2 = 4t − 4.
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.
319
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. (4)
i=1
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 Conclusion
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 l-
quasi-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.
References
[Arora, 1998] Arora, S. (1998). Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and
other geometric problems. Journal of the ACM, 45.
[Baburin et al., 2009] Baburin, A., Della Croce, F., Gimadi, E. K., Glazkov, Y. V., and Paschos, V. T. (2009).
Approximation algorithms for the 2-Peripatetic Salesman Problem with edge weights 1 and 2. Discrete Applied
Mathematics, 157(9):1988–1992.
[Baki, 2006] Baki, M. (2006). A new asymmetric pyramidally solvable class of the Traveling Salesman Problem.
Oper. Res. Lett., 34(6):613–620.
[Baki & Kabadi, 1999] Baki, M. and Kabadi, S. (1999). Pyramidal Traveling Salesman Problem. Computers &
Operations Research, 26(4):353–369.
[Balas, 1999] Balas, E. (1999). New classes of efficiently solvable generalized Traveling Salesman Problems.
Annals of Operations Research, 86:529–558.
[Balas & Simonetti, 2001] Balas, E. and Simonetti, N. (2001). Linear time dynamic-programming algorithms
for new classes of restricted TSPs: A computational study. INFORMS J. on Computing, 13(1):56–75.
[Berg et al., 2016] Berg, M. d., Buchin, K., Jansen, B. M. P., and Woeginger, G. (2016). Fine-Grained Com-
plexity Analysis of Two Classic TSP Variants. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Y. R. and
Sangiorgi, D., editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP
2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:14, Dagstuhl,
Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
320
[Burkard & Deineko, 1998] Burkard, R. and Deineko, V. (1998). On the Traveling Salesman Problem with a
relaxed Monge matrix. Inf. Process. Lett., 67(5):231–237.
[Burkard et al., 1998] Burkard, R. E., Deineko, V. G., van Dal, R., van, J. A. A., Veen, d., and Woeginger, G. J.
(1998). Well-solvable special cases of the Traveling Salesman Problem: a survey. SIAM Rev., 40(3):496–546.
[Chentsov et al., 2016] Chentsov, A. G., Khachai, M. Y., and Khachai, D. M. (2016). An exact algorithm with
linear complexity for a problem of visiting megalopolises. Proceedings of the Steklov Institute of Mathematics,
295(1):38–46.
[Christofides, 1975] Christofides, N. (1975). Worst-case analysis of a new heuristic for the Traveling Salesman
Problem. In Symposium on New Directions and Recent Results in Algorithms and Complexity, page 441.
[Enomoto et al., 1998] Enomoto, H., Oda, Y., and Ota, K. (1998). Pyramidal Tours with Step-backs and the
Asymmetric Traveling Salesman Problem. Discrete Appl. Math., 87(1-3):57–65.
[Gimadi et al., 2014] Gimadi, E. K., Glazkov, Y., and Tsidulko, O. Y. (2014). Probabilistic analysis of an
algorithm for the m-planar 3-index assignment problem on single-cycle permutations. Journal of Applied and
Industrial Mathematics, 8(2):208–217.
[Gimadi & Rykov, 2016] Gimadi, E. K. and Rykov, I. A. (2016). On the asymptotic optimality of a solution
of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Doklady
Mathematics, 93(1):117–120.
[Gutin & Punnen, 2007] Gutin, G. and Punnen, A. P. (2007). The Traveling Salesman Problem and Its Varia-
tions. Springer US, Boston, MA.
[Khachai & Neznakhina, 2015] Khachai, M. and Neznakhina, E. (2015). A polynomial-time approximation
scheme for the euclidean problem on a cycle cover of a graph. Proceedings of the Steklov Institute of Mathe-
matics, 289(1):111–125.
[Khachay & Neznakhina, 2016a] Khachay, M. and Neznakhina, K. (2016a). Approximability of the Minimum-
Weight k-Size Cycle Cover Problem. Journal of Global Optimization, 66(1):65–82.
[Khachay & Neznakhina, 2016b] Khachay, M. and Neznakhina, K. (2016b). Towards a PTAS for the generalized
TSP in grid cluster. AIP Conf.Proceedings, 1776(1):050003.
[Klyaus, 1976] Klyaus, P. (1976). Generation of Testproblems for the Traveling Salesman Problem (in Russian).
Preprint Inst. Mat. Akad. Nauk. BSSR, (16).
[Oda & Ota, 2001] Oda, Y. and Ota, K. (2001). Algorithmic aspects of pyramidal tours with restricted jump-
backs. Interdisciplinary Information Sciences, 7(1):123–133.
[Pardalos et al., 2013] Pardalos, P., Du, D., and Graham, R. (2013). Handbook of Combinatorial Optimization.
Springer.
[Sahni & Gonzales, 1976] Sahni, S. and Gonzales, T. (1976). P-complete approximation problems. Journal of
the ACM, 23:555–565.
321