The report presents certain successful examples of the implementation of an asymptotically optimal approach to the solving some largescale routing problems in which the author has been directly involved in the past half century. 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
This paper is a short survey on the efficient approximation algorithms with proven performance guarantees for some discrete routing problems that are NP-hard in general case. One of the most popular problems of this kind is the Travelling Salesman Problem (TSP) [Gutin, 2002]. The problem is MAX SNP-hard: existence of a polynomial approximation scheme for it yields P = N P .
Another problem considered is a problem of finding several edge-disjoint Hamiltonian circuits of extreme total edge weight. This problem is referred to as the m-Peripatetic Salesman Problem (m-PSP) was first mentioned in [Krarup, 1974]. The problem consists in finding m edge-disjoint Hamiltonian circuits Hi E; i = 1; m, in a complete undirected n-vertex graph G = (V; E) with weight functions wi : E ! R; i = 1; m, such that their total weight W1(H1) + : : : + Wm(Hm) is minimal (or maximal), where Wi(H) = ∑e∈H wi(e), i = 1; m.
De Kort [De Kort, 1991] showed that the problem of finding two edge-disjoint Hamiltonian circuits is NPcomplete. This result implies that the 2-PSP with identical weight functions is NP-hard in both maximization and minimization variants. The problem is also NP-hard for the case of different weight functions [Baburin et al., 2004].
De Brey and Volgenant [De Brey & Volgenant, 1997] identify several polynomially solvable cases of 2-PSP. De Kort [De Kort, 1991, De Kort, 1992, De Kort, 1993] designed and analyzed lower and upper bounds for the 2-PSP as possible ingredients of branch-and-bound algorithms. Duchenne, Laporte and Semet discussed a polyhedral approach for solving the m-PSP [Duchenne et al., 2005].
For the minimization problems we will use the notations m-PSPmin and m-PSPdmin (in the cases of identical and different weight function correspondingly). Similar notations m-PSPmax and m-PSPdmax will be used for the maximization problems. Denote by 2-PSP[1; q] the case of the problem where the weights of the edges are arbitarary numbers in the integer interval [1; q], and by 2-PSPr; q the case of the problem with weights r and q.
The paper is organized as follows. In section 2 we present the known approximation polynomial-time algorithms with performance guaratees for the 2-PSP on deterministic inputs. The following sections 3 – 6 are devoted to the realization of the asymptotically optimal approach for solving the difficult problems of combinatorial optimization under consideration. Section 3 describes two asymptotically optimal algorithms for solving the Euclidean TSPmax in the Euclidean space with fixed dimension space. The first algorithm uses the Serdyukov’s idea to transform an auxiliary structure — maximum weight matching — into a Hamiltonian circuit. The second algorithm is based on the new idea to use the solution of the maximum-weigt covering problem as an auxiliary structure. Section 4 discusses asymptotically optimal approach to solving some subclasses of the m-PSP: the maximum-weight m-PSP in the multidimensional Euclidean space, and the Random m-PSP with different and identical weight functions. In Section 5 the results are pesented for so-called TSP-approach to asymptotically optimal solving the NP-hard problem of Covering a Graph by a Given Number of Nonadjacent Cycles in the case of the maximum-weight problem in the multidimensional Euclidean space, and in the case of the minimum-weight problem on Random UNI(0,1) inputs. The last Section 6 contains some results for the Random Multi-index Assignment Problem which is NP-hard both in axial and planar versions. 2
This section presents the known results of constructing approximation polynomial-time algorithms with performance guaratees for the 2-PSP on deterministic inputs. Denote by At an algorithm A with approximation ratio t. 2.1
2-PSPmax: Algorithms A3=4 and A7=9
A polynomial approximation algorithm A3=4 with performance guarantee of 3=4 for solving the 2-PSPmax was presented in [Ageev et al., 2007]. First, a cubic (if n is even) or ”almost” cubic (if n is odd) 3-regular subgraph G3 of G of maximum total edge weight is constructed by Gabow’s algorithm [Gabow, 1983]. Then G3 is split into a partial tour and a 2-matching. Then the subgraphs are modified into two partial tours by regrouping their edges. The resulting partial tours can be converted to two edge-disjoint Hamiltonian circuits by adding the missing edges. The weight of the solution is at least (3=4) OP T , where OP T is the optimal weight. The performance guarantee relies on the facts that the total edge weight of G3 is at least (3=4) OP T and all the edges of G3 were included into the solution. The running time of the algorithm is determined by the time complexity of finding G3 in G and is bounded by O(n3) as described by Gabow [Gabow, 1983].
In [Glebov & Zambalaeva, 2011] it is presented a cubic time approximation algorithm A7=9 for this problem with guaranteed ratio 7=9. The starting point of the algorithm is finding a 4-regular subgraph G4 G of maximum edge weight using Gabow’s algorithm [Gabow, 1983]. Then a couple of edge-disjoint specific tours are found in G4 with a sufficiently large number of edges, further these tours are transformed to the tours with total weight at least (7=9) OP T and finally completed to edge-disjoint Hamiltonian cycles that correspond to approximate solution of the problem. 2.2
Metric 2-PSPmin: A9=4 and A2
It is supposed in this section that the triangle inequality holds: w(i; j) w(i; k) + w(j; k) for each vertices i; j; k 2 V . It is known that the problem 2-PSPmin is NP-hard even in the metric case and does not admit any constant-factor approximation in the general case.
A cubic time approximation algorithm A9=4 for the Metric 2-PSPmin was presented in [Baburin et al., 2004]. The performance ratio of this algorithm asymptotically tends to 9=4. Later an algorithm with the performance ratio 9=4 for the problem was also announced in [Croce et al., 2005].
The algorithm A2 of Ageev and Pyatkin [Ageev et al., 2007] first finds two edge-disjoint spanning trees (T1∗; T2∗) of minimum total weight. This can be done in O(n2 log n) time using the algorithm of Roskind and Tarjan [Roskind & Tarjan, 1985]. At Stage 1 they modify the pair of the trees (T1∗; T2∗) into the pair of trees (T1; T2) having the same edge set and construct the first Hamiltonian cycle H1, that is edge-disjoint with T2 and has a weight at most 2W (T1). At Stage 2 the second Hamiltonian cycle H2 is built such that is edge-disjoint with H1 and has a weight at most 2W (T2). Note that the graphs H1 [ T1 and H2 [ T2 are outer planar with outer faces H1 and H2 respectively. 2.3
For this problem the 12=5-approximation algorithm with time complexity O(n3) was presented in [Baburin et al., 2004]. Initially two approximate solutions H1 and H2 of the TSPmin with weight functions w1 and w2 respectively are found by the 3=2-approximation Christofides-Serdyukov’s algorithm. After that a second circuit H2 is transformed to H2′ such that H2′ is edge-disjoint with H1 and its weight is at most twice the weight of H1. Then the roles of graphs H1 and H2 change and the pair (H1; H2′) or (H1′; H2) of minimum total weight is chosen as an approximate solution for the problem considered. 2.4
2-PSPmin[1; q]
The problem 2-PSPmin[1; q] can be solved in O(n3)-time with performance ratio (4+q)=5 [Gimadi, 2008]. The key point of the proof of this result consists in the followingn (useful for construction and analysis algorithms) structure statement: in n-vertex 4-regular graph a pair of edge-disjoint partial with at least 8n=5 total number of edges can be found in quadratic time complexity. 2.5
It is clear that the 2-PSPminf1; 2g is a special case of the metric 2-PSPmin.
In [Croce et al., 2005] an algorithm with a performance ratio of about 1:37 was announced for this problem in assumption that the performance ratio 7=6 holds for a solution of the TSPminf1; 2g found by the algorithm presented in [Papadimitriou & Yannakakis, 1993].
In [Baburin et al., 2009] the following connection between maximization and minimization problems is shown: let there be a polynomial -approximation algorithm for the problem 2-PSPmax(0; 1). Then a (2 )-approximate solution for the 2-PSPmin(1; 2) can be found in polynomial time. Thus approximate solutions with total weight of at most 5=4 and 11=9 times the optimal for the 2-PSPmin(1; 2) can be found in O(n3) running-time using algorithms from [Ageev et al., 2007] and [Glebov & Zambalaeva, 2011] correspondingly.
An improved approximation ratio 6=5 results from the structure statement in previous section. 2.6
2-PSPmax[1; q] 2.7
2-PSPdmin(1; 2)
In [Gimadi & Ivonina, 2012] an improved approximation ratio (3q + 2)=(4q + 1) for solving the problem 2PSPmax[1; q] is achieved by a combined using of the 3=4-approximation algorithm for the 2-PSPmax and the 5=(q + 4)-approximation algorithm for the 2-PSPmin[1; q], that follows from [Gimadi, 2008]. It also gives the bound 8=9 for the problem with q = 2.
In [Gimadi, 2008] it is shown that a solution with performance ratio (1 + ′=2) can be obtained for the 2-PSPdmin(1; 2), where ′ is the approximation ratio for the problem TSPmin(1; 2). Using an algorithm from [Berman & Karpinski, 2006] with ′ = 8=7 for the TSPmin(1; 2) it is possible to find a feasible solution for the 2-PSPdmin(1; 2) with total weight of at most 11=7 times the optimal. Though the running time of the algorithm used is polynomial, it is very high: O(nK+4), where the constant K in [Berman & Karpinski, 2006] is equal to 21. Thus, using an 11=9-approximation algorithm for the TSP(1; 2) from [Papadimitriou & Yannakakis, 1993], we can obtain a 29=18-approximation algorithm, here the ratio is larger but the running time of the algorithm is much smaller. In this case, the time complexity is determined by one of the stages of the algorithm, where a minimum-weight cycle cover in G with edge-weights 1 and 2 is found. In [Papadimitriou & Yannakakis, 1993] it is proposed, that it can be done in O(n2:5).
In [Glebov & Zambalaeva, 2011] it is presented the 4=3-approximation algorithm with time complexity O(n4) for the 2-PSPdmin(1; 2). This result improves above mentioned performance guarantees 11=7 and 29=18. Algorithm is based on the ideas from [Serdyukov, 1987], where 8=7-approximation algorithm for the TSPmin with edge weights 1 and 2 is announced. In particular, a perspective charge technique is used, applying for prove structure theorems in graph theory. 2.8
2-PSPdmax(1; 2) Let there be an approximation algorithm with a ratio 1 for the 2-PSPdmin(1; 2). Using this ratio for the 2-PSPdmax(1; 2), the polynomial approximation algorithm can be constructed with the approximation ratio max = 1181 −−185 . Then the known bounds 11=7, 7=5 and 4=3 [Croce et al., 2005, Glebov & Zambalaeva, 2011, Glebov et al., 2011] are correspond the following estimations of the performance ratio max for the 2PSPdmax(1; 2): 16153 < 3571 < 2207 respectively [Gimadi & Ivonina, 2012]. 3
The problem TSP is called Euclidean if vertices in given graph G = (V; E) correspond to points in the Euclidean space Rk, and edge-weights equal to lengths between endpoints of relative intervals (edges).
It is known [Fekete&Barvinok] that the Euclidean TSPmax in space Rk is NP-hard when k 3. (For k = 2 hardness status of this problem is open).
Note, that the problem can be solved in O(n3) running time with the approximation ratio near 0:9 [Baburin & Gimadi, 2006].
Nevertheless for the Euclidean TSPmax there is an asymptotically optimal algorithm [Serdyukov, 1987] with
time complexity O(n3)
The idea of the algorithm is to transform an auxiliary structure — maximum weighted matching — into a Hamiltonian cycle by means of consecutive patching ”near-parallel” matching edges (intervals) into cycles. Preliminarily maximum weight matching is divided into heavy and light edges. At first the heavy edges are patched, and then the light edges are used.
The construction of a Hamiltonian cycle is based on the following instructive facts, which are true in any space Rd: (i) any sufficiently large set of vectors in Rd contains two almost parallel vectors; (ii) two almost parallel vectors can be replaced by a pair of different vectors with the same endpoints (crossways) with an only insignificant lost in the total length. 3.2
Recently a new polynomial-time asymptotically optimal algorithm for this problem was designed using another technique [Gimadi & Tsidulko, 2017]. In contrast to using the maximum matching mentioned above, it is suggested to use the maximum-weight cycle coverage C∗ = fC1; : : : ; C g as an auxiliary structure in G. The construction of C∗ is performed in time O(n3). In the case of = o(n) the cycle cover C∗ is transformed into an asymptotically optimal solution of the Metric TSPmax (see the equation (7) in [Gimadi et al., 2016]). In the case of = cn, c n=3 is constant, a subgraph Ge is build such that it induced by a set of minimal edges e1; : : : ; e (one in each cycle). Since this set is the maximum matching in Ge, it can be used as a “falsework” in Euclidean space for designing a set of edges to close the circuits C1 n e1; : : : ; C n e into the Hamiltonian cycle throuth all vertices of the inishial graph G in the Euclidean space Rk. 4 4.1 m-PSP
To solve the Euclidean problem of several traveling salespersons, the idea of an algorithm with an auxiliary construction in the form of the maximum matching is used: the 2-EPSPmax [Gimadi, 2008] and the m-EPSPmax [Baburin & Gimadi, 2010]. Note that the same maximum-weight matching intervals are used as “building material” or ”falsework” in constructing Hamiltonian cycles H1; : : : ; Hm.
On each step of the process a pair of “near-parallel“ edges is selected and the cycles that contain the pair are patched in the way that the length of the product cycle is maximum. In [Baburin & Gimadi, 2010] for solving m-EPSPmax an approximation algorithm with time complexity O(n3) and relative error O(( m ) k+21 ) n is constructed. So the algorithm is asymptotically optimal under the condition m = o(n) on the number of edge-disjoint Hamiltonian routs. 4.2
Algorithms with performance guaratees are obtained for the Random m-PSPmin in the complete graph with the uniform, exponential, and truncated-normal distribution of edge weights in the case of different weight functions of Hamiltonian cycles [Gimadi et al., 2014, Gimadi et al., 2015]. The algorithm with time complexity O(mn2) was used for the approximate solution of the problem with the number of salespersons m < n=4 in the case when elements of the input matrix are independent identically distributed random variables, which take values from domain [an; bn]; an > 0 (the parameter bn = 1 if distribution is exponential or truncated-normal).
The following conditions for asymptotic optimality was obtained: n=an = { oo((nn=)l,ninf)ln, nif 2 mm <n1l−n n; ; , where n is the parameter bn, n or n for the uniform, exponential and normal distributions, respectively.
The Random m-PSPmax with different weight functions, in the case of the uniform distribution on bounded interval [a; b], a 0, is solved asymptotically optimal independently on the boundaries of [a; b] [Gimadi & Tsidulko, 2017].
Similar results are true for distributions that dominate the cosidered distribution functions. 4.3
The results for the Random m-PSP with identical weight functions of the required subgraphs were obtained in [Gimadi et al., 2016]. Note that the probabilistic analysis of the algorithm from the previous subsection crucially depends on the independence of different weight functions of the salespersons. This is not the case for the mPSPmin with identical weight functions, since the weight functions in this case are obviously not independent. Therefore for this variant of the problem we cannot expect good results using the technique from the article [Gimadi et al., 2015].
For the m-PSP with identical weight functions a new algorithm was proposed in [Gimadi et al., 2016], which consists of the following three steps.
Step 1. Uniformly split the initial complete n-vertex graph G into subgraphs G1; : : : ; Gm, so that V (Gi) = V (G), and for each edge e 2 E(G) choose with equal probability 1=m a subgraph Gi, and put e to E(Gi).
Step 2. Construct subgraphs Ge1; : : : ; Gem deleting all edges in Gi; 1 i m, which are lighter than w′, where w′ is selected in a special way, though still providing enough edges in each Gei for the next Step 3.
Step 3. In each subgraph Gei build a Hamiltonian cycle, using a polynomial algorithm, that with high probability or whp (with probability ! 1 as n ! 1 finds a Hamiltonian cycle in a sparse random graph.
Conditions for the asymptotic optimality of the algorithm for random input data with uniform and exponential distributions are found.
Note that a new approach to solving the problem works both in the case of identical and in the case of the different weight functions. 5
A natural generalization of the TSP is the problem of finding a spanning subgraph consisting of exactly m cycles of extreme total weight (m-Cycles Cover Problem). The TSP is a special case of this problem for m = 1. Unlike a polynomially solvable problem (in time O(n3) [Gabow, 1983]) of a cyclic covering with an optimized number of cycles, a problem with a given number of cycles is NP-hard.
In [Gimadi et al., 2016, Gimadi & Rykov, 2016] an asymptotically optimal approach solving the Euclidean m-Cycles Cover Problem on maximum is presented. Suppose given an algorithm for solving the Euclidean max TSP. As such, we take the asymptotically optimal algorithm from the article [Gimadi, 2001]. This algorithm yields a Hamiltonian cycle. Let us represent this solution, the Hamiltonian cycle, as a sequence of vertices: He = f1; 2; : : : ; ng. The cycle lengths can be given as variables.
By an admissible partition of the vertices we mean a partition u = (u1; : : : ; um) into a family of nonadjacent segments (chains) Sk = (uk−1; uk); k = 1; 2; : : : ; m, such that 1 u1 < u2 < : : : < um n and each segment Sk contains at least two edges, i.e., uk uk−1 3; we set u0 = um.
We refer to the edges fuk; uk+1g between neighboring segments in a partition of the cycle as separating edges. We refer to the edges (chords) of the form fuk−1 + 1; ukg; k = 1; 2; : : : ; m, as closing edges. The addition of these edges transforms the family of segments into a cycle cover of the graph
It can be assumed that the sizes (numbers of vertices) Lk of cycles are fixed, or that they are variable. Algorithm for the Euclidean Max m-Cycles Cover Problem:
Step 1. Choose any uk such that Lk = uk uk−1 3. If some lengths of the cycles Lk are given, choose uk = uk−1 + Lk.
Step 2. Perform the rotation procedure: for each j from 0 to n 1, remove the edges fu1 + j; u1 + 1 + jg; fu2 + j; u2 + 1 + jg; : : : ; fum + j; um + 1 + jg from He and close the resulting chains into cycles. This procedure yields m cycles of lengths L1; : : : ; Lm. The admissible solution thus obtained is denoted by Cej .
Step 3. Choose the best cover among the n obtained solutions: W (Ce) = max W (Cej ). 0≤j<n
For m = o(n) the algorithm finds an asymptotically optimal solution of the Euclidean Max m-Cycles Cover problem in time O(n3).
TSP-approach to the construction of an approximation algorithm for the Random Min m-Cycles Cover Problem with random instances UNI(0; 1) is analyzed in [Gimadi et al., 2016]. It is shown that the problem is solved asymptotically optimal in time complexity O(n3) for the numbers of covering cycles m n1=3= ln n. 6
The MAP is NP-hard if the number of indexes is greater than 2 in both axial and planar cases [Spieksma, 2000]. 6.1
In the case of the axial MAP, n elements must be selected in the multi-index matrix such that in every cross-section exactly one element is chosen. The cross-section is set of matrix elements where one index is fixed.
For the multi-index axial Assignment Problem on random instances, asymptotic optimality conditions were established for a quadratic-time algorithm based on the choice of minimal element in the current line of a special matrix formed from the initial matrix [Baburin et al., 2004]. 6.2
In this case the problem deals with selection of n2 elements in a cubic matrix (cijk). Exactly one element in each line is chosen. A line is the set of n elements with two fixed indexes.
Conditions of asymptotic optimality were established for the m-layer three-index planar assignment problem on random input data when the number m of layers in the matrix (cijk) is at most O(ln n) [Baburin et al., 2004] and O(n ); 0 < < 1 [Gimadi & Glazkov, 2007, Gimadi et al., 2014].
Note that the m-layer three-index planar assignment problem on single-cyclic permutations coincides with the m-PSP with different weight functions. Consequently, the results of Section 3 are also valid for the problem under consideration.
The study of sections 3.2, 4.3 and 5 was partially supported by the Russian Science Foundation (project 16-1110041). The study of another sections was partially supported by the the Russian Foundation for Basic Research (projects 16-07-00168 and 15-01-00976), and the grant of Presidium of RAS (program 8, project 227).