Abstract
In this paper, we introduce the notion of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours to the case of the Generalized Traveling Salesman Problem (GTSP). We show that, for the instance of GTSP on n cities and k clusters with arbitrary weights, l-quasi-pyramidal and l-pseudo-pyramidal optimal tours can be found in time \(O(4^ln^3)\) and \(O(2^lk^{l+4}n^3)\), 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 l-quasi-pyramidal optimal tour (for some fixed value of l) is proved.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
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. [14, 19, 21]).
It is known that TSP is strongly NP-hard and hardly approximable in its general setting [22]. At the same time, the problem remains intractable in metric and Euclidean settings, but can be approximated well in these cases, admitting fixed-ratio algorithms for an arbitrary metric [10] and Polynomial Time Approximation Schemes (PTAS) for Euclidean spaces of any fixed dimension [1]. Many generalizations of TSP, e.g. Cycle Cover Problem [13, 15, 16], Peripatetic Salesman Problem [2, 12], have the similar approximation behaviour.
Algorithmic issues of finding optimal restricted tours, for several kinds of restrictions, e.g. precedence constraints, are also actively investigated (see, e.g. [4, 5, 9]). Among others, restriction of TSP to considering so called pyramidal tours (see e.g. [8]) seems to be especially popular. A pyramidal tour respects the initial order defined on the nodeset of a given graph and, for some r, has the form
where \( v_{i_j}<v_{i_{j+1}} \) for any \(j\in \{1,\ldots ,r-1\}\) and \(v_{i_j}>v_{i_{j+1}}\) for any \(j\in \{r+1,\ldots ,n-1\}\).
It is widely known [18] that an optimal pyramidal tour can be found in time of \(O(n^2)\) for any weighting function. Recently it was shown [6] that, for the Euclidean setting, an optimal pyramidal tour can be found in time \(O(n\log ^2n)\). In papers [11, 20], several generalizations of pyramidal tours, for which optimal tour can also be found efficiently were introduced. Despite their fame, pyramidal tours have one shortcoming. Known settings of TSP and its generalizations, for which the existence of optimal pyramidal tours is proven, 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. [14]) and some other special cases [3, 7, 19].
The contribution of this paper is two-fold. First, we introduce (in Sect. 2) notion of generalized pyramidal tours, we call them l-quasi- and l-pseudo-pyramidal, extending the classic notion of pyramidal tours and results of [20] to the case of Generalized Traveling Salesman Problem (GTSP). We show that l-pseudo-pyramidal and l-quasi-pyramidal optimal tours can be found in time \(O(2^lk^{l+4}n^3)\) and \(O(4^ln^3)\), respectively. Then, in Sect. 3, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of on optimal l-quasi-pyramidal tour (for some fixed l) is proved.
2 Generalized Pyramidal Tours
We proceed with the common setting of the Generalized Traveling Salesman Problem (GTSP). An instance of the GTSP is defined by a complete edge-weighted graph \(G=(V,E,w)\) with weighting function \(w:E\rightarrow \mathbb {R}_+\), and by a given partition \(V_1\cup \ldots \cup V_k=V\) of the nodeset \(V=V(G)\) of the graph G. Feasible solutions are cyclic tours \(\tau =(v_{i_1},\ldots ,v_{i_k})\) visiting each cluster \(V_i\) once. Hereinafter, we call such routes Clustered Hamiltonian tours or CH-tours. The problem is to find a CH-tour of the minimum weightFootnote 1.
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, (linearly) ordered finite set \((V_1,\ldots ,V_k)\) of clusters induces a partial order on the nodeset V of the graph G as follows: For any \(u\in V_{i}\) and \(v\in V_{j}\), \(u \prec v\) if \(i<j\).
Definition 1
Let \(\tau \) be a CH-tour
such that \(v_t\in V_t\) for any t. We call \(\tau \) an l-quasi-pyramidal tour, if \(i_p-i_q\le l\) and \(j_{p'}-j_{q'}\le l\) for any \(1\le p<q\le r\) and \(1\le p'<q'\le k-r-2\).
The following theorems extend the results proposed in [20] for the classic TSP.
Theorem 1
For any weighting function \(w:E\rightarrow \mathbb {R}_+\), a minimum cost l-quasi-pyramidal CH-tour can be found in time of \(O(4^ln^3)\).
Proof
We start with some necessary notation. For any integers \(i>j\), we use the common shortcuts [j, i], [j, i), and (j, i) for intersections with \(\mathbb {N}\) of the sets \(\{j,\ldots ,i\}\), \(\{j,\ldots ,i-1\}\), \(\{j+1,\ldots ,i-1\}\), respectively. For any nodes \(u\in V_i\) and \(v\in V_j\), \(i\ne j\), and an arbitrary subset \(S\subset [i-l,i)\setminus \{1,j\}\) or \(S\subset [j-l,j)\setminus \{1,i\}\), let g(v, S, u) be the weight of a shortest \((|S|+1)\)-edge path from u to v visiting all the clusters \(\{V_t:t\in S\}\) (see Fig. 1). Values of the function g can be easily calculated recursively, since \(g(v,\varnothing ,u)=w(\{v,u\})\) and
Further, for any \(1\le j<i\le k\), let f(u, v, T) be the weight of a shortest path P from \(u\in V_i\) to \(v\in V_j\) visiting all the clusters with numbers from \(([1,i)\cup [1,j))\setminus T,\) where \(T\subseteq ([i-l,i)\cup [j-l,j))\setminus \{1,i,j\}\), and the path P has the form
for pairwise defferent indexes \(i_0,\ldots , i_r,j_1,\ldots ,j_s\), such that \(\bar{v}\in V_1\), \(i_t<i\) for \(1\le t\le r\), \(j_{t'}<j\) for \(0\le t'\le s-1\), and
As with the function g, values of the function f can be obtained recursively. We start with values \(f(u,v,(1,t))=w(\{u,v\})\) for any \(u\in V_1\) and \(v\in V_t\), \(2\le t\le l+2\). All other necessary values f(u, v, T) for any \(u\in V_i\), \(v\in V_j\) and any \(T\subset ([i-l,i)\cup [j-l,j)) \setminus \{1,i,j\}\) can be computed in ascending order by i and \(j<i\) as follows. Let m be the maximum number of the cluster (excluding i and j) visited by the path P. If \(m>j\), then f(u, v, T) can be calculated by formula
and otherwise by
Finally, we obtain f(u, v, T) for any \(u\in V_k\) and \(v\in V_{k-1}\) and for any \(T\subseteq [k-l-1,k-1)\). Weight of an optimal l-quasi-pyramidal tour (see Fig. 2) is given by
We compute a naïve upper bound for time complexity of the algorithm. At first, we calculate the necessary values g(v, S, u) by formula (1) in time \(O(2^ln^3)\). Then, the initial values f(u, v, (1, t)) can be computed in \(O(n^2)\). Further, for any fixed u, v and T, the complexity of Eqs. (2) and (3) does not exceed \(O(2^ln)\). Since, formulas (2) and (3) are invoked at most \(O(2^ln^2)\) times, the overall time complexity bound is \(O(4^ln^3)\), which completes our proof.
Remark 1
Evidently, result of Theorem 1 can be considered in the context of 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 Sect. 3, we describe a subclass of geometric GTSP, each of 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 \(\tau \) be a CH-tour \(v_{1},v_{i_1},\ldots ,v_{i_r}, v_k, v_{j_{k-r-2}},\ldots ,v_{j_1}\) such that \(v_t\in V_t\) for any t. We call \(\tau \) an l-pseudo-pyramidal tour, if \(i_p-i_{p+1}\le l\) and \(j_{q}-j_{q+1}\le l\) for any \(1\le p\le r-1\) and \(1\le q\le k-r-3\).
It easy to verify that any l-quasi-pyramidal tour is an l-pseudo-pyramidal as well.
Theorem 2
For any weighting function \(w:E\rightarrow \mathbb {R}_+\), a minimum cost l-pseudo-pyramidal CH-tour can be found in time of \(O(2^lk^{l+4}n^3)\).
Proof
Our argument consists of two stages.
At the first stage, we enumerate all l-pseudo-pyramidal tours in an auxiliary complete graph \(H=K_k\) with vertex set \(\{1,\ldots ,k\}\), which we call graph of clusters. Denote the set of these tours by \(\varTheta _l\).
Then, at the second stage, for any tour \(\theta =(1,i_1,\ldots ,i_{k-1})\in \varTheta _l\) and any node \(u\in V_1\), we find a shortest u-u-path \(\rho (\theta ,u)\) in the appropriate auxiliary \((k+1)\)-partite graph \(H_{\theta ,u}\), which is defined as follows. Denote parts of \(H_{\theta ,u}\) by \(\pi _0,\ldots ,\pi _k\). Then, as it is shown at Fig. 3, \(\pi _0=\pi _k=\{u\}\) and, for any \(j\in [1,k)\), \(\pi _j\) coincides with the cluster \(V_{i_j}\) of the graph G, i.e. \(\pi _j=V_{i_j}\). For any \(j\in [0,k)\), the subgraph \(H_{\theta ,u}\langle \pi _j\cup \pi _{j+1}\rangle \) induced by \(\pi _j\) and \(\pi _{j+1}\) is a complete bipartite graph. The edges of the graph \(H_{\theta ,u}\) inherit the edge weights of the given graph G.
Evidently, any u-u-path in the graph \(H_{\theta ,u}\) is equivalent to the appropriate CH-tour in the graph G. Therefore, a minimum cost l-pseudo-pyramidal CH-tour in the graph G is defined by a shortest path \(\rho (\theta ^*,u^*)\), i.e.
The time complexity of both stages does not exceed the product of the complexity \(T(\varTheta _l)\) of the l-pseudo-pyramidal tours enumeration procedure for the graph H (construction of the set \(\varTheta _l\)), the size of \(V_1\), and the complexity of the shortest-path problem in graphs \(H(\theta ,u)\), i.e. \(O(k\cdot n^2)\). Hence, the overall time complexity will be at most \( T(\varTheta _l)\cdot O(n^3), \) since, without loss of generality, we can assume that \(|V_1|=\min \{|V_i|:i\in [1,k]\}\le n/k\).
To estimate \(T(\varTheta _l)\) we augment the dynamic programming procedure developed in [20].
We introduce two sets \(\varTheta _l^+\) and \(\varTheta _l^-\) of partial simple (possibly closed) paths in the graph H. Each element of \(\varTheta _l^+\) is a path \(\theta ^+=(i_1,\ldots ,i_c)\) such that \(i_p-i_{p+1}\le l\) for any \(p\in [1,c)\). Similarly, each element \(\theta ^-=(j_1,\ldots ,j_d)\in \varTheta _l^-\) satisfies the equation \(j_{q+1}-j_q\le l\) for any \(q\in [1,d)\).
The current state of the recursive procedure is encoded by a triple (i, S, E), whose entries is defined as follows. The number \(i\in [1,k-1]\) denotes depth of recursion. The set \(S=\{p_1,\ldots ,p_m\}\) consists of signed pairs \((i,j)\in [1,k]^2\) such that
-
(i)
\(p_1=(1,s)^+\) and \(p_2=(t,1)^-\) for some \(\{s,t\}\subset [1,k]\)
-
(ii)
there exists a set \(\varTheta (i,S)\) of partial paths \(\theta _1,\ldots ,\theta _m\), for which
-
\(\theta _a\) is a simple path from \(i_a\) to \(j_a\)
-
\(\theta _a\in {\left\{ \begin{array}{ll} \varTheta ^+_l\text{, } \text{ if } p_a=(i_a,j_a)^+\\ \varTheta ^-_l\text{, } \text{ if } p_a=(i_a,j_a)^-\end{array}\right. }\)
-
let \(I_a\) be the nodeset of the path \(\theta _a\); then, \(I_1\cap I_2=\{1\}\), and \(I_a\cap I_b=\varnothing \) for any other a and b
-
\(I_1\cup \ldots \cup I_m=[1,i]\).
-
Finally, the set E is an arcset of the l-pseudo-pyramidal tour to be constructed (for the convenience, we store edges of this tour with their bypass directions). Denote
The recursion starts from the following set of initial states (see Fig. 4)
Any time, when \(i>1\), there are the following six options. Consider them separately.
Case 1. There exists \(p=(i,i)^+\in S\) (or \((i,i)^-\)). In this simple case, we make a recursive call with the state \((i-1,S\setminus \{p\},E)\) immediately.
Case 2. There exists \(p_a=(i,j)^+\in S\). Then, in the path \(\theta _a\in \varTheta ^+_l\), the node i has a successor \(t\in [i-l,i-1]\). We make a recursive call with the state
for any \(t\in [i-l,i-1]\setminus (Q\setminus \{j\})\).
Case 3. There exists \(p_a=(i,j)^-\in S\). Then, in the path \(\theta _a\in \varTheta ^-_l\), there is a successor \(t\in [1,i-1]\), and we call the recursion with the state
for each \(t\in [1,i-1]\setminus (Q\setminus \{j\})\).
Case 4. There is \(p=(j,i)^+\in S\). This can be treated similarly to Case 3.
Case 5. There is \(p=(j,i)^-\in S\). This is similar to Case 2.
Case 6. In this case, \(i\not \in Q\), and we should try iteratively all elements of the set S. Suppose, i belongs to path \(\theta _a\) assigned to the pair \(p_a=(i_a,j_a)^+\in S\) such that \(s\in [1,i-1]\) is its predecessor, and \(t\in [i-l,i-1]\) is a successor. Then we should call the recursion with the state
for each \(s\in [1,i-1]\setminus (Q\setminus \{i_a\}\)) and \(t\in [i-l,i-1]\setminus (Q\setminus \{j_a\})\). Similarly, for the pair \(p_a=(i_a,j_a)^-\), we make a recursive call with states
for each \(s\in [i-l,i-1]\setminus (Q\setminus \{i_a\}\)) and \(t\in [1,i-1]\setminus (Q\setminus \{j_a\})\).
If \(i=1\), then \(S=\{(1,1)^+,(1,1)^-\}\), and the state (1, S, E) is final. In this case, E contains arcs of an l-pseudo-pyramidal tour, which can be decoded in time O(k).
Since, as it is shown in [20] the time complexity of the recursive procedure above is \(O(2^l k^{l+3})\), the overall complexity bound of finding the minimum cost l-pseudo-pyramidal tour is
Thus, the theorem is proved.
Remark 2
As with Theorem 1, Theorem 2 states that, for any weighting function, GTSP belongs to FPT with respect to parameters k and l. Also, since \(O(2^l(\log n)^{l+4}n^3)\) asymptotically does not exceed \(2^{O(l^3)}\cdot O(n^4)\), the problem has FPT algorithms with respect to parameter l only any time when \(k=O(\log n)\).
3 Polynomial Time Solvable Subclass of GTSP on Grid Clusters
In this section, we describe a polynomially solvable subclass of the 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\times 1\) cell of the grid forms a cluster. The weighting function is induced by distances between the respective points with respect to some metric. To simplify it, we consider Euclidean distances, but similar results can be easily obtained for some other metrics, e.g. for \(l_1\). In Fig. 5, we present an instance of the Euclidean GTSP-GC with 6 clusters.
For two special cases of the problem, when the number k of clusters is \(O(\log n)\) or \(n - O(\log n)\), polynomial time approximation schemes (PTAS) were proposed in [17]. Meanwhile, the question of a systematic description of polynomial time solvable subclasses of GTSP-GC, which is closely related to complexity analysis of the 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 the other one is unbounded). We call this case GTSP-GC(H2). We show that any instance of GTSP-GC(H2) has an l-quasi-pyramidal optimal 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 Tour straightening transformation (Algorithm 1), which is closely related to the well-known class of local search heuristics and is introduced in the following.
To describe the transformation, assign to columns of the grid defining the given instance of GTSP-GC(H2), integer numbers \(1,2,\ldots , W\) (from the left to the right). Consider an arbitrary CH-tour \(\tau \). Assigning to each node \(v_i\) of \(\tau \) the number \(c_i\) of the column it belongs to, obtain a sequence \(\sigma \) of column numbers presented in the order induced by the tour \(\tau \). Without loss of generality, assume that \(\sigma \) has the form
for some appropriate numbers r and s.
Suppose, for some integer number t, whose value will be specified later, there exist indices
In this case, we say that the tour \(\tau \) has a t-zigzag (Fig. 6). Obviously, any l-quasi-pyramidal tour contains no t-zigzags, for \(t\ge l\). Algorithm 1 replaces all segments of the tour \(\tau \) having t-zigzags with subtours of a special kind.
To specify the value of t, notice that the weight of eliminated segments of \(\tau \) has an evident lower bound
Meanwhile, the weight of their replacement in Step 7 at any iteration of Algorithm 1 is at most \(2t + 2F(Y,S_2)\), where \(F(Y,S_2)\) is an optimum value of the 2-medians clustering objective function for a sample Y taken from the line segment \(S_2=\{y:0\le y\le 2\}\).
To estimate an upper bound for \(F(Y,S_2)\) we need the following technical lemma.
Lemma 1
For any sample \(\xi =(p_1,\ldots , p_n)\), \(p_i\in S_1=\{p: 0\le p\le 1\}\) there exist numbers \(m_1\) and \(m_2\in S_1\) such that
We give a short sketch of the proof of Lemma 1 postponing its full version to the forthcoming paper. Without loss of generality, we assume that any sample \(\xi =(p_1,\ldots ,p_n)\) contains points \(p_i\) in ascending order. Moreover, we assume that any cluster \(C=\{i_1,\ldots ,i_\mu \}\subset [1,n]\) inherites this property, i.e. \(p_{i_1}\le \ldots \le p_{i_\mu }\) and \(p_i\le p_j\) holds for any partition \(C_1\cup C_2=[1,n]\) and any \(i\in C_1\) and \(j\in C_2\). Then, for the median m of a \(\mu \)-points cluster C we obtain
Therefore, for a given sample \(\xi \), the value \(F(\xi ,S_1)\) depends on the choice of a partition \(C_1\cup C_2 = [1,n]\) ultimately and obeys the equation
Thus, \(\sup _{\xi \in S_1^n}F(\xi ,S_1)\) coincides with an optimum value \(q^*(n,S_1)\) of linear program (8)
Applying to program (8) the recurrent variable elimination technique, it is easy to verify that \(q^*(n,S_1)\le n/6\), which completes the sketch of our proof.
Getting back to discussion of Algorithm 1, we obtain from Lemma 1 that
Therefore, at any iteration of Algorithm 1, the tour \(\tau '\) becomes cheeper if
Further, let the cells of the grid be ordered as in Fig. 8 (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 have proved the following theorem.
Theorem 3
Any instance of GTSP-GC(H2) has an optimal 20-quasi-pyramidal CH-tour.
As a consequence of Theorems 1 and 3, we obtain that GTSP-GC(H2) can be solved to optimality in time \(O(n^3)\).
4 Conclusion
In this paper, the new notions of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours are 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 the unit 2-row rectangular grid on the Euclidean plane. However, the trick with 2-medians can not be applied straightforward even to the case \(h=3\), we believe that we can soon prove the existence of l-pseudo-pyramidal optimal tours for the case of GTSP-GC(Hh) defined by a grid of an arbitrary fixed height h.
Notes
- 1.
In this paper, we restrict ourselves to the case of undirected graphs. Nevertheless, the analogous argument can be provided to the case of digraphs and asymmetric weighting functions w.
References
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753–783 (1998)
Baburin, A., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.T.: Approximation algorithms for the 2-Peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157(9), 1988–1992 (2009)
Baki, M.F.: A new asymmetric pyramidally solvable class of the traveling salesman problem. Oper. Res. Lett. 34(6), 613–620 (2006). http://www.sciencedirect.com/science/article/pii/S0167637706000022
Balas, E.: New classes of efficiently solvable generalized Traveling Salesman Problems. Ann. Oper. Res. 86, 529–558 (1999)
Balas, E., Simonetti, N.: Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study. INFORMS J. Comput. 13(1), 56–75 (2001). https://doi.org/10.1287/ijoc.13.1.56.9748
de Berg, M., Buchin, K., Jansen, B.M.P., Woeginger, G.: Fine-grained complexity analysis of two classic TSP Variants. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 5:1–5:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). http://drops.dagstuhl.de/opus/volltexte/2016/6277
Burkard, R.E., Glazkov, Y.V.: On the traveling salesman problem with a relaxed monge matrix. Inform. Process. Lett. 67(5), 231–237 (1998). http://www.sciencedirect.com/science/article/pii/S0020019098001197
Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev. 40(3), 496–546 (1998)
Chentsov, A.G., Khachai, M.Y., Khachai, D.M.: An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Ins. Math. 295(1), 38–46 (2016). https://doi.org/10.1134/S0081543816090054
Christofides, N.: Worst-case analysis of a new heuristic for the Traveling Salesman Problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)
Enomoto, H., Oda, Y., Ota, K.: Pyramidal tours with step-backs and the asymmetric Traveling Salesman Problem. Discrete Appl. Math. 87(1–3), 57–65 (1998)
Gimadi, E.K., Glazkov, Y., Tsidulko, O.Y.: Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations. J. Appl. Ind. Math. 8(2), 208–217 (2014)
Gimadi, E.K., Rykov, I.A.: On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math. 93(1), 117–120 (2016)
Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Boston (2007)
Khachai, M., Neznakhina, E.: Approximability of the problem about a minimum-weight cycle cover of a graph. Doklady Math. 91(2), 240–245 (2015)
Khachay, M., Neznakhina, K.: Approximability of the minimum-weight k-Size cycle cover problem. J. Glob. Optim. 66(1), 65–82 (2016). https://doi.org/10.1007/s10898-015-0391-3
Khachay, M., Neznakhina, K.: Towards a PTAS for the generalized TSP in grid clusters. AIP Conf. Proc. 1776(1), 050003 (2016). https://doi.org/10.1063/1.4965324
Klyaus, P.: Generation of testproblems for the Traveling Salesman Problem. Preprint Inst. Mat. Akad. Nauk. BSSR (16) (1976). (in Russian)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics & Optimization. Wiley, Chichester (1985)
Oda, Y., Ota, K.: Algorithmic aspects of pyramidal tours with restricted jump-backs. Interdisc. Inform. Sci. 7(1), 123–133 (2001)
Pardalos, P., Du, D., Graham, R.: Handbook of Combinatorial Optimization. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1
Sahni, S., Gonzales, T.: P-complete approximation problems. J. ACM 23, 555–565 (1976)
Acknowledgements
This research was supported by Russian Science Foundation, project no. 14-11-00109.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Khachay, M., Neznakhina, K. (2017). Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10627. Springer, Cham. https://doi.org/10.1007/978-3-319-71150-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-71150-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71149-2
Online ISBN: 978-3-319-71150-8
eBook Packages: Computer ScienceComputer Science (R0)