arXiv:1009.5030v1 [cs.CC] 25 Sep 2010  Approximability of the Multiple Stack TSP  Sophie Toulouse   1  LIPN (UMR CNRS 7030) - Institut Galil ́ ee - Universit ́ e Paris 13, 99 av. Jean-Baptiste Cl ́ ement, 93430 Villetaneuse, France  Abstract  STSP seeks a pair of pickup and delivery tours in two distinct networks, where the two tours are related by LIFO contraints. We address here the problem approxima- bility. We notably establish that asymmetric MaxSTSP and MinSTSP12 are   APX , and propose a heuristic that yields to a 1/2, 3/4 and 3/2 standard approximation for respectively Max2STSP, Max2STSP12 and Min2STSP12.  Keywords:   Approximation algorithms, multiple stack TSP, TSP, LIFO constraints  1   Introduction  The   multiple Stack Traveling Salesman Probem , STSP, has been recently in- troduced in [ 1 ] and is very well motivated by the initial request of a trans- portation company. Consider a company that owns a vehicle fleet and a depot in   m   distinct cities   C 1 , . . . , C m . For any pair ( C j   , C j ′   ) of cities, the company handles orders from   C j   suppliers to   C j ′   customers, proceeding as follows: in  C j   , a single vehicle picks up all the orders that involve a   C j ′   customer; during this tour, the commodities are packed within a single container that consists of a given number   k   of rows; the container is then sent to   C j ′   , where a local vehicle delivers the commodities. The operator thus is faced with two levels of  1   Email:   sophie.toulouse@lipn.univ-paris13.fr
transportation: the local one inside the cities, the long-haul one between the cities. STSP models the local level problem; namely, in the context we have just described, every pair of cities defines an instance of STSP. The problem specificity relies on the way the containers are managed: their rows behave like stacks, and   no repacking   is allowed. The rows of the containers thus are subject to LIFO   “Last In First Out”   constraints. Therefore, the delivery tour in   C j ′   must handle   at first   orders that have been handled   at last   in   C j   . Formally, an instance   I   of STSP considers a number   k   of stacks (the container rows), together with two distinct networks   I A   = ( G A , d A ) , I B   = ( G B   , d B   ), where   V   ( G α )   ≡   [ n   + 1] and   d α   :   E ( G α )   →   N ,   α   ∈ { A, B } . In both networks, vertex 0 represents the depot, whereas vertex   i   ∈   [ n ] represents the   i th order (the   i th supplier in   I A , the   i th customer in   I B   ).   A solution consists of a pickup tour   ~ T   A   on   I A , a delivery tour   ~ T   B   on   I B   , and a packing  P   =   { P   1 , . . . , P   k }   of the commodities into the stacks, where a stack   P   β   is described as a sequence ( i 1 , . . . , i p β   ) of commodities (index 1 refers to the bot- tom of   P   β   ). We denote by   < α , α   ∈ { A, B }   the complete order that   ~ T   α   induces on [ n ]:   i < α   i ′   iff   ~ T   α   handles order   i   earlier than it handles   i ′ . Similary, we denote by   < P   the partial order that   P   induces on [ n ]:   i < P   i ′   iff   P   stacks   i  at a lower position than   i ′   in a same stack   P   β .   The LIFO constraints may thus be expressed in terms of the three orders   < A ,   < B   ,   < P   . Namely, a triple ( P , ~ T   A , ~ T   B   ) is consistent   iff   it satisfies:  ∀ i   6   =   i ′   ∈   [ n ] , i < P   i ′   ⇒   ( i < A   i ′ )   ∧   ( i > B   i ′ ) (1) The value of a solution ( P , ~ T   A , ~ T   B   ) is given by the sum   d A (   ~ T   A ) +   d B   (   ~ T   B   ) of the distance of its two tours. The ultimate goal naturally consists in finding the feasible triple ( P , ~ T   A , ~ T   B   ) of optimum value. In what follows, the stacks are assumed to have   unlimited capacities . The most often, input graphs are complete.   For TSP ( the Traveling Salesman Problem ), as well as for STSP, A(S)TSP, ∆(S)TSP and (S)TSP ab   respec- tively refer the asymmetric, the metric and the bivaluated cases.   Finally,  k STSP considers that   k   is a universal constant. Since one manipulates both maximization and minimization goals, we use notations    ,   ≻ ,   opt ,   opt   in- stead of   ≥ ,   > , max, min ( resp. ,   ≤ ,   < , min, max) if the goal is to maximize ( resp. , to minimize). Finally, because one jointly considers pickup and delivery tours, we respectively denote by   E − 1   =   { ( i ′ , i )   |   ( i, i ′ )   ∈   E } ,   G − 1   = ( V, E − 1 ),  d − 1   :   E − 1   →   N   :   d − 1 ( i, i ′ ) =   d ( i ′ , i ) and   I − 1   = ( G − 1 , d − 1 ) the reverse of an edge set   E , a graph   G   = ( V, E ), a distance   d   :   E   →   N , a network   I   = ( G, d ). Hence,   ~ T   is a tour of value   d (   ~ T   ) on   I   iff   ~ T   − 1   is a tour of value   d (   ~ T   ) on   I − 1 .
2   Preliminaries  The problem trivially is   NP   −   hard , from TSP. Indeed, for extremal val- ues of the number of stacks, STSP strictly is equivalent to TSP: if STSP assumes a single stack, then it reduces to TSP, considering the distance  d   : ( i, i ′ )   7   →   d A ( i, i ′ ) +   d B   ( i ′ , i ); if on the opposite STSP assumes   n   stacks, then it reduces to two independent TSP (packings that store one commodity per stack do not induce any LIFO constraint). The litterature on computa- tional aspects of STSP is rather thin: see [ 1 , 2 ] for metaheuristic approachs, [ 3 ] for an exact approach (that solves 2STSP via the computation of the   k  best tours in   I A , I B   ), [ 4 ] for an analysis of STSP complexity. We here make use of natural connections to TSP and observations made in [ 4 ] in order to locate STSP within the approximation hierarchy. Besides its practical impacts, STSP presents a rather intricate combina- torial structure.   One the one hand, one could wonder on what part of the problem does structure / impact the most the solution / its complexity.   It appeared in [ 4 ] that both the packing and the tour subproblems are tractable:  Theorem 2.1 ([ 4 ])   In arbitrary input graphs:  (i)   Deciding, given a pair   (   ~ T   A , ~ T   B   ) , whether it admits or not a consistent packing   P   (and to design this packing if the answer is YES) is in   P .  (ii)   When   k   is a universal constant:   given a packing   P , computing a pair of tours that are optimal for   P   is in   P .  On the other hand, STSP has strong connections to   coloring   and   schedul- ing . Indeed, subproblem ( i ) reduces to graph coloring in   C (   ~ T   A , ~ T   B   ) =   { i   6   =  i ′   ∈   [ n ]   |   i < A   i ′   ⇔   i < B   i ′ } , whereas subproblem ( ii ) reduces to scheduling under   < P   (or   > P   ) precedence constraints.  3   A first classification of STSP  Property 1   (i)   There exists a standard approximation preserving reduction from ASTSP to ATSP that maps a   ρ -approximate solution of ATSP to a   ρ/ 2 ,   ρ/ 2 + ( a/ 2 b ) ,   ρ/ 2 + ( b/ 2 a ) -approximate solution of ASTSP for Max(S)TSP, Max(S)TSP ab   and Min(S)TSP ab , respectively.  (ii) Case of arbitrary graphs.   Any approximate factor   ρ   for any restriction of STSP also holds for the same restricton of TSP.  Proof.   i . Associate with the instance   I   = ( I A , I B   ) of ASTSP the pair ( I A , I B   )
( i )  i 1  j  ?   i 1  j ′   i 1  j  ?   i 1  j ′  i 2  h  i 2  h ′  ( ii )  i 1  j   i 1  j ′  i 2  h  i 2  h ′  ?  ( iii )  i 1  j   i 1  j +1  i 2  h +1 i 2  h  ?  i 1  j   i 1  j +1  i 2  h +1 i 2  h  ?  Fig. 1. The three configurations that contradict consistency.  of instances of ATSP. Compute   ~ T   α , α   ∈ { A, B }   an approximate tour on   I α . Pick the tour   ~ T   A   or   ~ T   B   that performs the best among   d A (   ~ T   A ) + ( d B   ) − 1 (   ~ T   A ), ( d A ) − 1 (   ~ T   B   ) +   d A (   ~ T   B   ).   ii . Associate with the instance   I   = ( G, d ) of TSP the instance   I ′   = ( I, I − 1 ) of STSP.   ✷  Proposition 3.1 (Immediate from Property   1 )  (i) Max(A)STSP, Max ∆ (A)STSP, Max(A)STSP01, Min(A)STSP12 are standard-approximable within the following factor: MaxSTSP   MaxASTSP   Max ∆ STSP   Max ∆ ASTSP  61 / 162   −   o (1) , [ 8 ]   1 / 3 , [ 9 ]   7 / 16   −   o (1) , [ 7 ]   31 / 80 , [ 10 ] MaxSTSP01   MaxASTSP01   MinSTSP12   MinASTSP12  3 / 7 , [ 12 ]   3 / 8 , [ 11 ]   11/7, [ 12 ]   13/8, [ 11 ] (ii)   Max ∆ STSP ∈   MaxSNP -hard, [ 5 ]; MaxSTSP12 ∈   APX -hard, [ 6 ]; Min- STSP is not   2 p ( n +1)   standard-approximable for any polynomial   p , or   P   =   NP  4   A matching based heuristic for the symmetric 2STSP  In what follows, we say that an edge set   N   is   consistent   with a packing   P   iff  there exists a completion   N ′   of   N   into a tour   T   s.t.   T   is feasible with respect to   P . We first provide a characterization of consistency for 2STSP.  Proposition 4.1 (Due to lack of space, the proof is omitted.)   Given a packing   P ,   J β   =   { 0 , . . . , p β   + 1 }   denotes the index set on   P   β ,   β   ∈ { 1 ,   2 } . Arti- ficial indexes   0 , p β   +1   are introduced in order to represent the depot vertex,   i.e. ,  i β  0   =   i β p β   +1   = 0 . Let   N   be a collection of pairwise disjoint elementary chains on  [ n   + 1] , then   N   is consistent with   P   iff   it satifies the three following properties (configurations that contradict consistency are illustrated in Figure   1 ):  (i)   No jump:   ∀ β   ∈ { 1 ,   2 } ,   ∀ j < j ′   ∈   J β   ,  (  { i β j   , i β j ′   } ∈   N  )  ∨  (  ∃ h   ≤   h ′   ∈   J 3 − β   ,   { i β j   , i 3 − β h   , . . . , i 3 − β h ′   , i β j ′   } ⊆   N  )  ⇒   j ′   =   j   + 1 (ii)   No crossing edges:   ∀ j   6   =   j ′   ∈   J 1 ,   ∀ h   6   =   h ′   ∈   J 2 ,   {{ i 1  j   , i 2  h } ,   { i 1  j ′   , i 2  h ′   }} ⊆   N  ⇒   ( j < j ′   ⇔   h < h ′ ) (iii)   No way back:   ∀ j   ∈   J 1 ,   ∀ h   ∈   J 2 ,   {{ i 1  j   , i 1  j +1 } ,   { i 2  h , i 2  h +1 }} ⊆   N  ⇒   ( { i 1  j   , i 2  h } )   / ∈   N   ∧   ( { i 1  j +1 , i 2  h +1 } )   / ∈   N
P   1   :  P   2   :  c 1 1   = 0  c 1 2  c 1 3  c 2 1   c 2 2  c 2 3 c 2 4  c 3 1  c 3 2  c 4 1   c 4 2   c 4 3  c 4 4 c 4 5 c 4 6  M   A  T   A , T   B   \ M   α  M   B  e ∗  B   A  A  B   0  Fig. 2. Possible completions of the approximate packing   P : case   n   even.  j, j ′   6   = 1 , j   ≡   j ′   + 1[2]  0  c 1 2   c 1 3   c 1 4   c 1 5   c 1 6  c 1 7 c 1 8 c 1 9  e ∗  j, j ′   6   = 1 , j   ≡   j ′ [2]  0  c 1 2   c 1 3   c 1 4   c 1 5   c 1 6  c 1 9 c 1 8 c 1 7  0  e ∗  j ′   = 1  0  c 1 2   c 1 3   c 1 4  c 1 5 c 1 6 c 1 7 c 1 8 c 1 9  0 e ∗   M   A  M   B  Fig. 3. The approximate packing when   n   is even and   p   = 1.  The algorithm relies on a pair ( M A , M B   ) of optimum weight matchings on   I A , I B   . Given such a pair, together with some additional edge   e ∗ , it aims at computing a packing   P   s.t.   N α , α   ∈ { A, B } , is consistent with   P , where  N α   coincides with   M α   ( resp. ,   M α   ∪ { e ∗ } ) when   n   is odd ( resp. , even). Let   H  denote the multigraph ([ n +1] , M A   ∪ M B   ), and   C 1 , . . . ,   C p   denote its connected components. We assume   w.l.o.g. , that the depot vertex ( i.e. , node 0) coincides with vertex   c 1 1   in   C 1 . If   n   is odd ( iff   n   + 1 is even), then every component   C h   is an elementary cycle   { c h  1   , . . . , c h q h   , c h  1   }   of even length   q h   ≥   2. Otherwise,   C h   =  { c h  1   , . . . , c h q h   , c h  1   }\{{ c h ℓ   , c h ℓ +1 }}   is an elementary chain of even length   q h   −   1   ≥   0 for a lonely index   h   ∈   [ p ]. We define the additional edge   e ∗   as follows:  ∀ p,   e ∗   = arg   opt {   opt  α = A,B  { d α ( f   ) } |   f   ∈   F   ( p ) } , where: (2)  F   (1) =   {( { 0 } ∪ { c 1 3 , . . . , c 1  ℓ   } )   ×   ( { 0 } ∪ { c 1  ℓ +1 , . . . , c 1  n } )}   \{{ 0 ,   0 }} (3)  F   ( p ) =   ∪ p  ( h<h ′ )=1 V   ( C h )   ×   V   ( C h ′  ) (4) The heuristic is described in Algorithm   1 : it first computes   M α , α   ∈ { A, B }  (Step ( i )) and   e ∗   (case   n   even, Step ( ii )); it then builds the approximate packing   P   by considering the components the one after each other, starting with   C 1   (Step ( iv )); it finally computes the best tours   T   α ( P ) , α   ∈ { A, B } , with respect to the   P   (Step ( v )).   Note that before it operates the packing, the algorithm may have in Step ( iii ) to perform some reindexation of the   C h , depending on   e ∗   (notably, if   p   ≥   2, then the two connected components that are incident to   e ∗   must be stacked consecutively). The even case is illustrated in Figures   2   ( p   ≥   2) and   3   ( p   = 1).  Claim 4.2   (i)   Algorithm   1   has polynomial-time complexity.  (ii)   N α , α   ∈ { A, B } , is consistent with the approximate packing   P .  (iii)   The solutions returned by the algorithm are   3 / 2 ,   3 / 4   and   1 / 2   standard ap- proximate for Min2STSP12, Max2STSP12 and Max2STSP, respectively; these ratios are (asymptotically) tight.
Algorithm 1.   An appproximate algorithm for 2STSP. (i) Compute   M   α   an optimum weight matching on   I α , α   ∈ { A, B }  (ii) Determine the connected components of   H   in such a way that   c 1 1   = 0  If   n   is even   Then   compute   e ∗   = arg   opt { opt α = A,B   { d α ( f   ) } |   f   ∈   F   ( p ) }  (iii)   If   n   is even and   p   ≥   2   Then   consider the components in such a way that: (a)   If   V   ( e ∗ )   ∩   V   ( C 1 )   ∈ {∅ ,   { 0 }}   Then   ∃ h   ∈   [ p ] \{ 1 }   s.t.   e ∗   =   { c h  ⌈ q h   / 2 ⌉ , c h +1 1   }  Else   e ∗   =   { c 1  j   , c 2 1 }   //   h   is taken modulo   [ p ] ,   j   ∈ { 2 , . . . , q 1 }   depends on   c 1 1  (b)   If   q 2   6   = 2   ∧   e ∗   =   { c 1  j   , c 2 1 } ∧ ∃ α,   {{ 0 , c 1 2   } ,   { c 2 1   , c 2  q 2   }} ⊆   M   α   Then   reverse   C 2  (iv)   If   n   is odd or   p   ≥   2 :  j 1   ←   ( If   n   ≡   0[2]   ∧   e ∗   =   { c 1  j   , c 2 1 }   Then   j :   ⌈ ( q 1   −   1) / 2 ⌉   + 1   otherwise )  j 2   ←   ( If   n   ≡   0[2]   ∧   e ∗   =   { c 1 2 , c 2 1 } ∧   q 2   = 2   Then   q 2 :   ⌈ q 2 / 2 ⌉   otherwise )  P   1   ←   ( c 1 2 , . . . , c 1  j 1   ,   c 2 1 , . . . , c 2  j 2   ,   c 3 1 , . . . , c 3  ⌈ q 3 / 2 ⌉   , . . . , c p  1 , . . . , c p  ⌈ q p   / 2 ⌉ )  P   2   ←   ( c 1  q 1   , . . . , c 1  j 1 +1 , c 2  q 2   , . . . , c 2  j 2 +1 , c 3  q 3   , . . . , c 3  ⌈ q 3   / 2 ⌉ +1   , . . . , c p q p   , . . . , c p  ⌈ q p   / 2 ⌉ +1 )  Else   (thus   p   = 1,   e ∗   =   { c 1  j   , c 1  j ′   } ,   j   ∈ { 1 }∪{ 3 , . . . , ℓ } , j ′   ∈ { 1 }∪{ ℓ +1 , . . . , n +1 } ) : If   j, j ′   6   = 1 and   j   ≡   j ′   + 1[2]   Then   P   1   ←   ( c 1 2 , . . . , c 1  ℓ   ),   P   2   ←   ( c 1  n +1 , . . . , c 1  ℓ +1 )  Else If   j, j ′   6   = 1 and   j   ≡   j ′ [2]   Then   P   1   ←   ( c 1 2 , . . . , c 1  ℓ   ),   P   2   ←   ( c 1  ℓ +1 , . . . , c 1  n +1 )  Else If   j ′   = 1   Then   P   1   ←   ( c 1 2 , . . . , c 1  j   ),   P   2   ←   ( c 1  n +1 , . . . , c 1  j +1 )  Else If   j   = 1   Then   P   1   ←   ( c 1 2 , . . . , c 1  j ′ − 1 ),   P   2   ←   ( c 1  n +1 , . . . , c 1  j ′   ) (v) Compute   T   α ( P ) , α   ∈ { A, B } , the best feasible tour for   P   = ( P   1 , P   2 ) on   I α  C h  ⌈ q h / 2 ⌉ −   1  ⌈ q h / 2 ⌉  ⌈ q h / 2 ⌉   + 1  e ∗  C h +1  1   2  q h +1  C h  ⌈ q h / 2 ⌉ −   1  ⌈ q h / 2 ⌉  ⌈ q h / 2 ⌉   + 1  e ∗  C h +1  1   2  q h +1  C 1  0   2  q 1  e ∗  C 2  1   2  q 2  M   A  M   B  Fig. 4. Case   n   even and   p   ≥   2: edge   e ∗   induces   “no jump”   in   M   α .  Proof. Claim ( i ).   Step ( v ) only requires a   O (( n +1) 2 )-time, [ 4 ]; for the other steps, the fact is either famous, or trivial.   Claim ( ii ).   N α , α   ∈ { A, B }   triv- ially satisfies Properties ( ii ) and ( iii ) ( resp. , ( i )) of Propositon   4.1 , in any case ( resp. , when   n   is odd or   p   = 1). Thus assume   n   ≡   0[2] and   p   ≥   2. Steps ( iii - a ) and ( iv ) of the algorithm indicate:   ∃ h   ∈   [ p ] ,   ∃ j   ∈   [ q h ]   s.t.   e ∗   =   { c h j   , c h +1 1   }   and  e ∗   ∈   P   1   ×   ( P   1   ∪ { 0 } ).   M α   possibly links   c h j   ( resp. ,   c h +1 1   ) to vertices (when they exist)   c h j − 1 , c h j +1   ( resp. ,   c h +1 1   , c h +1  q h +1   ), with   c h j − 1   ∈   P   1   (unless   e   =   { c 1 2 , c 2 1 } ),  c h j +1   ∈   P   2 ,   c h +1 2   ∈   P   1   and   c h +1  q h +1   ∈   P   2   (unless   e ∗   =   { c 1 2 , c 2 1 }   and   q 2   = 2). More- over, Steps ( iii - b ) and ( iv ) ensure that   P   satisfies:   ¬ ( { 0 , c 1 2 } ∈   M α   ∧{ c 2 1 , c 2  q 2   } ∈  M α )   ∧   ( c 2 1 , c 2  q 2   )   ∈   P   1   ×   P   2 ).   Hence, the chain   { c h j − 1 , c h j   , c h +1 1   , c h +1  q h +1   }   ( resp. ,
{ c h j +1 , c h j   , c h +1 1   , c h +1 2   } ) may never jump   c h j +1   ( resp. ,   c h +1  q h +1   ) in   P   2   (see Figure   4  for some illustration).   Claim ( iii ).   Let ( P ∗ , T   A, ∗ , T   B, ∗ ) ( resp. , ( P , T   A , T   B   )) denote an optimum ( resp. , the approximate) solution, we denote by   OP T  resp. ,   AP X ) its value; we observe: (i)   ∀ α   in   { A, B } ,   ∃   N ′ α   s.t.   T   ′ α   =   N α   ∪   N ′ α   is a tour, and   T   ′ α   is consistent with   P . By optimality of   T   α   with respect to   P , we thus have:  d α ( T   α )      d α ( M α ) +   d α ( N ′ α ) + 1 n ≡ 0[2] d α ( e ∗ ) , α   ∈ { A, B } . (ii) If   n   is odd, then any tour on [ n   + 1] is the union of two perfect matchings on [ n   + 1]. By optimality of   M α , we thus have: 2 d α ( M α )      d α ( T   α, ∗ ). (iii) If   n   is even, then   ∀   T   tour on [ n   + 1],   ∀ e   ∈   T   ,   T   \{ e }   is the union of two almost perfect perfect matchings on [ n   + 1]. Furthemore, by connectivity of   T   α, ∗ ,   ∃ e α   ∈   T   α, ∗   ∩   F   ( p ) , α   ∈ { A, B } .   By optimality of   M α , we thus have: 2 d α ( M α )      d α ( T   α, ∗ )   −   d α ( e α ). From ( i ), ( ii ), ( iii ), we deduce: 2 AP X      OP T   + 2   ∑  α  d α ( N ′ α ) + 1 n ≡ 0[2] (2   ∑  α  d α ( e ∗ )   −   ∑  α  d α ( e α )) (5) What enables to conclude for Max2STSP, when   n   is odd. When   n   is even, just observe that   e ∗   is optimal on   F   ( p ), whereas   e α   ∈   F   ( p ) , α   ∈ { A, B } :  ∑  α  d α ( e ∗ )      opt  α  { d α ( e ∗ ) }    opt  α  { d α ( e α ) }    1 / 2   ∑  α  d α ( e α ) (6) For the bivalued case, any edge set   S   satisfies   | S | ≤   d α ( S )   ≤   2 | S | , α   ∈ { A, B } . When   n   is odd, thus consider   | T   α, ∗ |   =   n   + 1 =   | N ′ α |   and conclude: 1 / 2 OP T   ≤   2( n   + 1)   ≤   2   ∑  α  d α ( N ′ α )   ≤   4( n   + 1)   ≤   2 OP T (7) When   n   is even,   | N ′ α |   =   n . Let   Q   denote the quantity 2( d A ( e ∗ )+ d B   ( e ∗ )) −  ( d A ( e A ) +   d B   ( e B   )):   if the goal is to maximize, assume that   Q <   2; then  d A ( e ∗ ) +   d B   ( e ∗ ) = 2 and   d A ( e A ) +   d B   ( e B   )   ≥   3, what contradicts the fact that  e ∗   is optimal. Similary,   Q   may not reach values 5 ,   6 when minimizing. Tight instances   I n,a,b   are defined on   K n +1 , n   ≥   1, as:   d α ( u, v ) =   a   if ( v   =  u +2 ∧ u   ≡   1[4]) or ( v   =   u +2 ∧ u   ≡   0[4] ∧ α   =   A ) or ( v   =   u +2 ∧ u   ≡   2[4] ∧ α   =   B ) or ( v   =   u   + 1   ∧ u   ≡   1[2]   ∧ α   =   A ) or ( v   =   u   + 1   ∧ u   ≡   0[2]   ∧ α   =   B ),   d α ( u, v ) =   b  otherwise. We consider subfamilies   I n,a,b   s.t.   ( a, b ) = (1 ,   0) ( resp. , (2 ,   1), (1 ,   2)) for Max2STSP ( resp. , Max2STSP12, Min2STSP12) and   n   = 8 q   −   1 ( resp. , 8 q ) for the odd ( resp. , even) case.   ✷  Theorem 4.3 (Immediate form Claim   4.2 )   Min2STSP12, Max2STSP12 and Max2STSP respectively are   3 / 2 ,   3 / 4   and   1 / 2   standard approximable.
5   Conclusion  Two main questions arise from the proposed analysis: Min∆STP approxima- bility, STSP differential approximability.  References  [1] Petersen H.L., Madsen O.B.G.: The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches. EJOR 198(1): 139-147 (2009) [2] Felipe A., Ortu ̃ no M., Tirado G.: New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks. TOP 17(1):190-213 (2009). [3] R. Lusbyz, J. Larsenz, M. Ehrgott, D. Ryan: An Exact Method for the Double TSP with Multiple Stacks. Report 2.2009 DTU Management Engineering (2009). [4] S. Toulouse, R. Wolfler Calvo: On the complexity of the multiple stack TSP,  k STSP. TAMC 2009, LNCS 5532:360-369 (2009). [5] A. Barvinok, D. S. Johnson, G. J. Woeginger, R. Woodroofe: The Maximum Traveling   Salesman   Problem   Under   Polyhedral   Norms.   IPCO   VI,   LNCS 1412:195-201 (1998). [6] C.H.   Papadimitriou,   M.   Yannakakis:   The   traveling   salesman   problem   with distances one and two. Mathematics of Operations Research 18:1-11 (1993). [7] Z.-Z. Chen, T. Nagoya: Improved approximation algorithms for metric MaxTSP. J. of Combinatorial Optimization 13(4):321-336 (2007). [8] Z.-Z.   Chen,   Y.   Okamoto,   L.   Wang:   Improved   deterministic   approximation algorithms for Max TSP. Inform. Proc. Letters 95(2):333-342 (2005). [9] H. Kaplan, N. Shafrir, M. Lewenstein, M. Sviridenko: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. J. of the ACM 52(4):602-626 (2005). [10] M. Bl ̈ aser, L. Shankar Ram, M. Sviridenko: Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. Operations Research Letters 37(3):176-180 (2009). [11] M. Bl ̈ aser: A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. APPROX-RANDOM 2004 LNCS 3122:61-71 (2004). [12] P. Berman; M. Karpinski: 8/7-approximation algorithm for (1,2)-tsp. SODA 2006, ACM 641-648 (2006).