On Modification of an Asymptotically Optimal Algorithm for the Maximum Euclidean Traveling Salesman Problem

Abstract

The known asymptotically optimal algorithm for the Euclidean maximum Traveling Salesman Problem by Serdukov builds approximate solution for the problem around the maximum-weight perfect matching. In this paper we are going to discuss an asymptotically optimal algorithm for the Euclidean maximum TSP with running-time $O(n^3)$, that uses a maximum weight cycle cover of the initial graph as a foundation for constructing the TSP solution. We also prove a number of structural results for the optima of some maximization problems in normed spaces, which follow from the algorithm.

Supported by Russian Science Foundation (project 16-11-10041).

1 Introduction

The Traveling Salesman Problem (TSP) is one of the most well-known NP-hard problems. Given an n-vertex undirected complete graph G(V, E) and a weight function $w: E \rightarrow \mathbb {R}^+$, the problem is to find a Hamiltonian cycle H of minimum or maximum total weight:

$$\begin{aligned} W(H) = \sum _{e \in H} w(e) \rightarrow \max \, (\min ). \end{aligned}$$

We refer the reader to the books [10] and [7] for the detailed overview of the known results on the problem. Historically, the most attention was paid to the minimization variant of the TSP, but the maximum TSP is also of great interest [1]. The Max TSP has many applications including the shortest superstring problem [9], matrix reordering in data analysis and clustering [8, 11]. Both Max TSP and Min TSP are NP-hard in the general case, so there is no much hope to obtain fast (polynomial time) exact algorithms for these problems. Thus, the study of special subclasses of the problem is an important aspect in the field of operations research.

One of the most studied sub-classes is the Metric Max TSP, where the weights of edges satisfy the triangle inequality. Another important variant of the problem is the Euclidean Max TSP (Max ETSP). In this case the vertices of a given graph correspond to points in $\mathbb {R}^k$ for some $k \ge 1$ and the weight of each edge is determined by the Euclidean distance between its endpoints. It is known that Max ETSP is NP-hard, if the dimension of the space $k \ge 3$ [2].

In 1987 Serdukov [12] presented the first polynomial-time asymptotically optimal algorithm for the Max ETSP. Later the algorithm was modified and simplified in [5, 6].

Definition 1

An approximation algorithm A for a maximization problem is said to have a guaranteed relative error $\varepsilon _A$, if

$$\begin{aligned} \frac{OPT(X)-F_A(X)}{OPT(X)} \le \varepsilon _A \end{aligned}$$

for any input X, where $F_{A}(X)$ is the value of the approximate solution obtained by algorithm A, and OPT(X) is the optimum.

Definition 2

For an optimization problem on an n-vertex graph, an approximation algorithm is called asymptotically optimal if the relative error is a function of the number of vertices n, and $\varepsilon _{A}(n) \rightarrow 0$ as $n \rightarrow \infty$.

Asymptotically optimal algorithms for the Max ETSP from papers [5, 6, 12] start with constructing the maximum weight matching $M^*$, which can be represented as a set $\{e_1,\ldots ,e_\mu \} \subset \mathbb {R}^k$ of (closed) straight intervals in Euclidean space, $\mu =\lfloor n/2\rfloor$. The intervals are sorted in non-decreasing order of their weights (length). Choosing parameter t in a spacial way, the last t intervals are declared light, while the remaining intervals are declared heavy. The following lemma establishes a fact that was crucial for proving the asymptotic optimality of these algorithms.

Lemma 1

([12]). Suppose that an arbitrary set of t straight line segments is given in Euclidean space $\mathbb {R}^k$ of fixed dimension k. Then, the smallest angle between two segments from this set is upper bounded by a constant $\alpha (k,t)$ such that $\alpha (k,t) \rightarrow 0$ as $t \rightarrow \infty$. Moreover

$$\begin{aligned} \sin ^2 \frac{\alpha (k,t)}{2} \le \frac{\gamma _k}{t^{2/(k-1)}} , \end{aligned}$$

(1)

where the constant $\gamma _k\le (k \sqrt{\pi }/2)^{\frac{2}{k-1}}$.

The heavy and light edges in the algorithm $A_{E}$ from [12] are used to form a multigraph $\overline{G}$ (see Fig. 1), that consists of four Hamiltonian cycles $H_1, H_2, H_3, H_4$, where each $H_i$ contains all the edges of $M^*$. The structure of these Hamiltonian cycles differs in cases of odd and even $\mu$. The output of the algorithm $A_{E}$ is the heaviest of the four Hamiltonian cycles. In case of odd n, at the final step of the algorithm vertex $v \notin M^*$ is arbitrary inserted into the constructed cycle.

The key points used in [12] to prove the asymptotic optimality of the algorithm $A_{E}$ when $t = \lceil { n^\frac{k-1}{k+1}}\rceil$ are Lemma 1 and the fact that the total weight of the heavy edges is at least $(1-\frac{t}{\mu } )W( M^*)$.

Fig. 1.

Multigraph $\overline{G}$ from [12]. Heavy edges of $M^*$ are represented by bold vertical lines, and light edges are represented by thin vertical lines. The numbers refer to the number of copies of the corresponding edges in the multigraph $\overline{G}$.

Later a new more simple version $A'$ of algorithm $A_{E}$ was presented in [5, 6]. In contrast to $A_{E}$, an asymptotically optimal solution obtained by algorithm $A'$ does not contain the edges of the maximum weight matching. This circumstance later played an essential role in implementing the asymptotically optimal approach to such an important generalization of the Traveling Salesman Problem as the Euclidean Maximum m-Peripatetic Salesman Problem [3]. In the latter work, the edges of maximal matching are used as the foundation in constructing each of m edge-disjoint traveling salesmen routes.

In this paper we discuss a new modification of the Serdukov’s approach for the Euclidean Max TSP, that starts with constructing an optimal cycle cover. In Sect. 2 we describe the algorithm. In Sect. 3.1 we prove that the algorithm is asymptotically optimal in the Euclidean space, and as a structural corollary we show that in the Euclidean space the weight of optimal solution to the maximum cycle cover problem and the double weight of the maximum weight matching are asymptotically equal. In Sect. 3.2 using the approach from [13] we show that the results obtained in the previous section can be extended to the case of an arbitrary normed space.

2 Modified Algorithm $\widetilde{A}$ Based on Maximum Cycle Cover

In this section we construct the main algorithm $\widetilde{A}$ for the Max TSP with running-time $O(n^3)$, that uses maximum weight cycle cover $C^*=(C_1, C_2, \ldots , C_\mu )$ of the initial graph as a foundation for constructing the solution to TSP. The analysis of algorithm $\widetilde{A}$ will be given in Sect. 3.

2.1 Description of Algorithm $\widetilde{A}$

Stage 1. Given a complete n-vertex complete undirected graph G, construct a cycle cover $C^* = (C_1, C_2, \ldots , C_\mu )$ of maximum total weight. Let $\mu$ be the number of cycles in this cover. If $\mu = o (n)$, go to Stage 2. Otherwise, perform Stage 3.

Stage 2. (The case $\mu = o(n)$). Run the following $\mu$-stage procedure to transform the optimal cycle cover $C^*$ into a Hamiltonian cycle H. Let $C'= C^*$.

At each step of the procedure, find the lightest edge $a = (a_1, a_2)$ in the set of edges $C'$ and the heaviest edge $b = (b_1,b_2)$ among the edges of all cycles in $C'$ that do not contain a. Combine 2 cycles, that contain edges a and b, into one cycle by replacing the edges a, b with the heaviest pair of edges: either $(a_1, b_1) \cup (a_2, b_2)$ or $(a_2, b_1) \cup (a_1, b_2)$. Stop when the edges of $C'$ form one cycle, which is clearly a Hamiltonian cycle. Set $H=C'$, output H.

Stage 3. (The case of $\mu =O(n)$).

• 3.1. Select an edge $e_i$ of minimum weight in each cycle $C_i$ of the cycle cover $C^*$, $i = 1, \ldots , \mu$. Let $C = \big \{C_1 \setminus e_1 , \ldots , C_\mu \setminus e_\mu \big \}$ be the family of remaining chains.

• 3.2. Let $V'$ be the set of vertices of the selected edges, $|V'| = 2\mu$. Let $G'~=~G[V']$ be the corresponding induced subgraph of G. Note that $M'=\{e_1, \ldots , e_{\mu }\}$ is a maximum weight perfect matching in $G'$.

• 3.3. In subgraph $G'$ construct a Hamiltonian cycle $H'$ that doesn’t contain edges $\{e_1, \ldots , e_{\mu }\}$. The detailed implementation of this step will be given in Subsect. 2.2 (Algorithm $A'$ [5]).

• 3.4. The obtained Hamiltonian cycle $H'$ consists of two perfect matchings $M_1'$ and $M_2'$. Denote by ${\widetilde{M}}$ the matching with a larger total weight.

• 3.5. As a result of Stage 3 return the Hamiltonian cycle $H = C \cup \widetilde{M}$ (see Fig. 2).

Fig. 2.

The Hamiltonian cycle $H = C \cup \widetilde{M}$. The bold curves are the chains of C. The bold lines correspond to the edges of $\widetilde{M}$. The dashed lines together with $\widetilde{M}$ form Hamiltonian cycle $H'$ in subgraph $G'$.

2.2 Algorithm $A'$: Constructing Hamiltonian Cycle $H'$ in $G'$

Preliminary Step

Recall that the edges $\{e_1,\ldots ,e_\mu \}$ in the $2\mu$-vertex graph $G'$ form the perfect matching $M'$ of maximum weight. Fix parameter $t\le \mu /2$. Sort the edges of $M'$ in non-decreasing order with respect to their weights. We will refer to the first ($\mu - t$) edges of $M'$ as heavy edges, and the last t edges as light.

Algorithm $A'$ constructs a Hamiltonian cycle $H'$, which does not include edges of $M'=\{e_1,\ldots ,e_\mu \}$, in $G'$.

Stage 1. Let angle $\alpha =\alpha (k, t)$ satisfy inequality (1).

Definition 3

An $\alpha$-chain is a sequence of edges (intervals in $\mathbb {R}^k$), where the angle between any two neighboring edges of the sequence is at most $\alpha$. The first edge in the sequence is called the master edge, and the last one is the inferior edge.

We are going to build a set $\mathcal {I}$ of $\alpha$-chains. Each $\alpha$-chain will consist only of heavy edges. Note that an edge is a one-element $\alpha$-chain.

Start with $\mathcal {I}=\{e_1,e_2,\ldots ,e_{t}\}$ consisting of the first t heaviest edges of $M'$. Set $j = t$. In the current t-set $\mathcal {I}$, find a pair of $\alpha$-chains such that the angle between their master edges is at most $\alpha$. Join these chains into one $\alpha$-chain by setting their master edges to be neighbors in the new sequence and assign one of the end edges of the joined chain (one of the former inferior edges) to be the new master edge. Set $j := j + 1$. If $j < \mu -t$, then append one more heavy edge $e_j$ to the current set $\mathcal {I}$ and repeat this block.

Otherwise, we have obtained a sequence $\mathcal {C}'=\{C_1',\ldots , C_{t}'\}$ of $t \$ $\alpha$-chains such that each chain consists of a sequence of heavy edges, where an angle between any neighboring (consecutive) pair of edges in this chain is at most $\alpha =\alpha (k,t)$.

Stage 2. Let’s regard the sequence $\mathcal {C}'$ as a cycle, i.e. the $\alpha$-chain $C_{t}'$ is followed by the $\alpha$-chain $C_1'$. Let the edges of the $\alpha$-chains $C_1',\ldots , C_{t}'$ be enumerated so that $C_r'=\{e_{\nu _{r-1}+1},\ldots ,e_{\nu _{r}-1}\},$$1\le r\le t,$ where $\nu _1<\nu _2<\ldots <\nu _{t}$ are the numbers reserved for the remaining light edges of the maximum weight matching $M'$ ($\nu _0=0, \ \nu _{t}=\mu$).

Fig. 3.

The bold lines correspond to the edges of $M'$, while the dashed lines indicates the $\alpha$-chains. The t light edges of $M'$ were placed to the positions between the $\alpha$-chains. The last light edge $e_{\nu _t}$ is placed between the first and the t-th $\alpha$-chains.

Arbitrary place t light edges of the maximum weight matching $M'$ to the positions $\nu _1,\nu _2,\ldots ,\nu _{t}=\mu$. Finally, we have a sequence $\mathcal {S}=\{C_1',e_{\nu _1},C_2',e_{\nu _2},\ldots , C_{t}',e_{\nu _{t}}\}$ of $t \$ $\alpha$-chains consisting of heavy edges, which alternate with the t light edges (Fig. 3).

Stage 3. Construct Hamiltonian cycle $H'$ in the following way.

We assume that the sequence of edges of the maximum weight matching $M'=\{e_1, e_2,\ldots , e_\mu \}$ is given according to their order in the sequence $\mathcal {S}$, $e_j=(x_j,y_j), \ j=1,\ldots ,\mu$. Now we are going to construct a partial tour T consisting of the end vertices of the light edge $e_\mu =(x_\mu ,y_\mu )$ and of two $(\mu -1)$-vertex paths.

Fig. 4.

The bold lines correspond to the edges of $M'$, the dashed lines correspond to the partial tour. We connect each two neighboring edges of $M'$ with the edges of the partial tour in a best possible way. Note that the edges of the perfect matching are not included to the partial tour.

• Step 1. Set $T=x_\mu \cup y_\mu ; \ u_1:=x_1; \ v_1:=y_1$ and $j=2$.

• Step 2. While $1< j<\mu$ do: if

  $$\begin{aligned} w(u_{j-1},x_j) + w(v_{j-1},y_j)\ge w(u_{j-1},y_j) + w(v_{j-1},x_j), \end{aligned}$$

  then set $u_j=x_j; \ v_j=y_j$; otherwise, set $u_j=y_j$ and $v_j=x_j.$ Supplement the partial tour T with a pair of new edges (Fig. 4) and increase j by 1:

  $$\begin{aligned} T:=T\cup (u_{j-1},u_{j})\cup (v_{j-1},v_{j}) . \end{aligned}$$

• Step 3. At the previous step we have obtained a partial tour consisting of the end vertices of the light edge $e_\mu =(x_\mu ,y_\mu )$ and of the two non-intersecting paths $(u_1,u_2,\ldots ,u_{\mu -1})$ and $(v_1,v_2,\ldots ,v_{\mu -1})$:

  $$\begin{aligned} T=(u_1,u_2,\ldots ,u_{\mu -1}) \cup (v_1,v_2,\ldots ,v_{\mu -1})\cup \{x_\mu \} \cup \{y_\mu \} . \end{aligned}$$

Close T into a $2\mu$-vertex cycle (Fig. 5) by adding a pair of two-edge chains $(u_{\mu -1},y_\mu ,v_1)\cup (v_{\mu -1},x_\mu ,u_1)$ or $(u_{\mu -1},x_\mu ,v_1)\cup (v_{\mu -1}, y_\mu ,u_1)$ with the greatest total weight.

The description of the algorithm $A'$ is complete.

Fig. 5.

The partial tour is closed into a Hamiltonian cycle $H'$, according to the best of two possible variants

Theorem 1

([5]). Let $G'$ be an undirected $2\mu$-vertex complete graph in Euclidean space $\mathbb {R}^k$ of a fixed dimension. Set parameter $t = \lceil { (2\mu )^\frac{k-1}{k+1}}\rceil$. Algorithm $A'$ builds an asymptotically optimal solution $H'$ in $G'$ for the Max ETSP. The relative error $\varepsilon _{A'}(n)$ of algorithm $A'$ satisfies:

$$\begin{aligned} \varepsilon _{A'}(n') \le \frac{\beta '}{ (n')^{\frac{2}{k+1}}} , \end{aligned}$$

(2)

where $n'=2\mu , \, \beta '\le (k \sqrt{\pi }/2)^{\frac{2}{k-1}}$. The total weight of the approximate solution $H'$ satisfies:

$$\begin{aligned} 2W(M')(1 - \varepsilon _{A'}(n')) \le W(H') \le 2W(M') , \end{aligned}$$

(3)

where $M'$ is the maximum weight perfect matching in $G'$.

Remark 1

The obtained Hamiltonian cycle $H'$ consists of 2 perfect matchings $M_1$ and $M_2$. Note that by construction of $H'$, $M' \cup M_1$ and $M' \cup M_2$ are also Hamiltonian cycles. Thus, adding $M_1$ or $M_2$ to the set of chains $C = C^* \setminus M'$ at Step 3.5 of the main algorithm $\widetilde{A}$ gives a Hamiltonian cycle in the initial graph G (see Fig. 2).

3 Asymptotic Optimality of Algorithm $\widetilde{A}$

3.1 The Case of Euclidean Space

Next statement shows the asymptotic optimality of algorithm $\widetilde{A}$ in the case of $\mu =o(n)$ for the Metric Max TSP and the Euclidean Max TSP.

Theorem 2

In the case of $\mu =o(n)$, algorithm $\widetilde{A}$ gives asymptotically optimal solutions for the Metric Max TSP and the Euclidean Max TSP with guaranteed relative error

$$\begin{aligned} \varepsilon _{\widetilde{A}}(n) \le \frac{\mu }{n}. \end{aligned}$$

(4)

Proof

Consider the procedure from Stage 2 of the algorithm, that transforms the optimal cycle cover $C^*$ into a Hamiltonian cycle $\widetilde{H}$. In the beginning of the procedure we have the set of edges $C'= C^*$. At each step of the procedure, the lightest edge $a = (a_1, a_2)$ in the set $C'$ and the heaviest edge $b = (b_1,b_2)$ among the edges of all cycles, that does not contain a, are chosen. The cycles containing a and b are united into one cycle by replacing the edges a and b by the pair of edges of maximum total weight: either $u=(a_1, b_1)$ and $v=(a_2, b_2)$ or $c = (a_1, b_2)$ and $d = (a_2, b_1)$. By the triangle inequality we have

$$\begin{aligned} w(b) \le w(u) + w(c) \quad \text{ and } \quad w(b) \le w(v) + w(d). \end{aligned}$$

Summing these inequalities, we obtain

$$\begin{aligned} 2w(b)\le w(u) + w(v) + w(c) + w(d) \end{aligned}$$

and, therefore,

$$\begin{aligned} w(b) \le \max \big (w(u) + w(v), w(c) + w(d)\big ). \end{aligned}$$

Thus, the new pair of edges compensate the weight of the heaviest edge b, and the loss of weight does not exceed the weight w(a) of the lightest edge.

After $\mu$ steps, we obtain a Hamiltonian cycle H, and the total loss of weight does not exceed the weight of $\mu$ lightest edges of $C^*$, which is at most $(\mu /n) W( C^*)$. Thus,

$$\begin{aligned} (1 - \mu /n) W( C^*) \le W(H) \le W(H^*) \le W(C^*) , \end{aligned}$$

(5)

where $H^*$ is the maximum weight Hamiltonian cycle. Finally, for the relative error we have:

$$\begin{aligned} \varepsilon _{\widetilde{A}}(n)=\frac{W(H^*)-W(H)}{W(H^*)}=1-\frac{W(H)}{W(H^*)}\le 1-\frac{(1-\frac{\mu }{n})W(C^*)}{W(H^*)}\le \frac{\mu }{n} . \end{aligned}$$

Next claim shows the asymptotic optimality of algorithm $\widetilde{A}$ in the case of $\mu =O(n)$ for the Euclidean Max TSP.

Theorem 3

In the case of $\mu =O(n)$, algorithm $\widetilde{A}$ gives an asymptotically optimal solution for the Euclidean Max TSP, if the dimension k of the Euclidean space $\mathbb {R}^k$ is fixed. The relative error satisfies

$$\begin{aligned} \varepsilon _{\widetilde{A}}(n)=\frac{\varepsilon _{A'}(n')}{3} \le \frac{\beta }{ (n')^{\frac{2}{k+1}}}, \end{aligned}$$

(6)

$n'=2\mu$, $\mu =O(n)$, $\beta \le (k \sqrt{\pi }/2)^{\frac{2}{k-1}}/3$.

Proof

Let $M^*$ be the maximum weight perfect matching, $C^*$ be the maximum weight cycle cover, and $H^*$ be the maximum weight Hamiltonian cycle in the given graph.

At Step 3.1 algorithm $\widetilde{A}$ deletes the lightest edge $e_i$ from each cycle $C_i$ in the cycle cover $C^*$ and sets $M'=\{e_1, \ldots e_{\mu }\}$. Since each cycle in the cycle cover consists of at least 3 edges, from $W(C_i)\ge 3 w(e_i)$ for all $i=1,\ldots ,\mu$, it follows that:

$$\begin{aligned} W( C^*)\ge 3 W( M'). \end{aligned}$$

Using (3), for the matching $\widetilde{M}$, which is the heaviest matching in the Hamiltonian cycle $H'$ formed at Step 3.3 of algorithm $\widetilde{A}$, we have:

$$\begin{aligned} W(\widetilde{M}) \ge \frac{W(H')}{2} \ge \frac{2 \big (1-\varepsilon _{A'}(n')\big ) W(M') }{2}= \big (1-\varepsilon _{A'}(n')\big ) W(M'). \end{aligned}$$

Finally, due to the construction of the desired Hamiltonian cycle H, the relative error of algorithm $\widetilde{A}$ is

$$\begin{aligned} \begin{array}{c} \varepsilon _{\widetilde{A}}(n) = 1 - \frac{W(H)}{W(H^*)} \le 1 - \frac{W(H)}{W(C^*)} = 1 - \frac{W(C^*\setminus M') + W(\widetilde{M})}{W(C^*)} \\ \le 1 - \frac{W(C^*\setminus M') +\big (1-\varepsilon _{A'}(n')\big ) W( M')}{W(C^*)}= 1 -\frac{W(C^*) -\varepsilon _{A'}(n') W(M')}{W(C^*)}\\ =\frac{\varepsilon _{A'}(n') W(M')}{W(C^*)}\le \frac{\varepsilon _{A'}(n')}{3}\le \frac{\beta }{ (n')^{\frac{2}{k+1}}}. \end{array} \end{aligned}$$

Remark 2

The running-time of algorithm $\widetilde{A}$ is determined by the time one needs to construct a maximum weight cycle cover $C^*$, which is $O(n^3)$ [4].

Remark 3

For the practical use of algorithm $\widetilde{A}$ one can set the following threshold in choosing between Stages 2 and 3. If the number of cycles $\mu$ in optimal the cycle cover at most $n^{\frac{k+1}{k+3}}\left( \beta ^{k+1}/4 \right) ^{\frac{1}{k+3}}$, perform Stage 2, otherwise perform Stage 3. In this case for the total relation error of the algorithm we have:

$$\begin{aligned} \varepsilon _{\widetilde{A}}(n) \le \left( \frac{\beta ^{k+1}}{4n^2}\right) ^{\frac{1}{k+3}} . \end{aligned}$$

Corollary 1

Let $M^*$ be the maximum weight perfect matching, $C^*$ be the maximum weight cycle cover, and $H^*$ be the maximum weight Hamiltonian cycle of an n-vertex complete graph G(V, E) in Euclidean space of fixed dimension. Then

$$\begin{aligned} 2W(M^*) = W(H^*)(1+o(1)) = W(C^*)(1 + o(1)) . \end{aligned}$$

In other words, in Euclidean space of fixed dimension the weights of the optimal $C^*, H^*$ and the doubled weight of $M^*$ are asymptotically equal.

Proof

The first equality follows from (3) for an n-vertex graph. The second equality follows from (5) and from the proof of Theorem 3, where having:

$$\begin{aligned} 1 - \frac{W(H)}{W(C^*)} \le \frac{\beta }{ (n')^{\frac{2}{k+1}}} \qquad \text {and} \qquad W(C^*) \ge W(H^*) \ge W(H) \end{aligned}$$

we obtain $W(C^*) = W(H^*)(1 + o(1))$.

3.2 The Case of an Arbitrary Normed Space

In 2014 Shenmaier [13] introduced the notation of a remote angle $\alpha (x,y)$ between two vectors x and y in an arbitrary normed space:

$$\begin{aligned} \alpha (x,y)= \min \{ \Vert x/\Vert x\Vert -y/\Vert y\Vert \Vert , \Vert x/\Vert x\Vert +y/\Vert y\Vert \Vert \}. \end{aligned}$$

He proved that substituting the angle, defined by the dot product, with the remote angle $\alpha (x,y)$ in Serdukov’s algorithm [12] (or its modification [5]), one can obtain an asymptotically optimal algorithm $A_N$ for the Max TSP in an arbitrary normed space. The relative error of algorithm $A_N$ is $\varepsilon _{A_N} \le (k+1)/\lfloor n^{\frac{1}{k+1}} \rfloor$, where k is the dimension of the space.

It is easy to see that due to the same modifications our algorithm $\widetilde{A}$ would also give asymptotically optimal solutions to the Max TSP in an arbitrary normed space. First note, that in the case of small number of cycles in the optimal cycle cover ($\mu =o(n)$) according to Theorem 2 algorithm $\widetilde{A}$ is asymptotically optimal in any metric space. For the case of large number of cycles in the optimal cycle cover ($\mu =O(n)$) the asymptotic optimality follows strictly from Theorem 3 and the result by Shenmaier [13].

Corollary 2

Using the remote angle instead of an angle, defined by the dot product, at Step 3.3, our algorithm $\widetilde{A}$ also gives asymptotically optimal solutions for the Max TSP in an arbitrary normed space. The relative error of the algorithm in the case of executing Stage 3 is $\varepsilon _{\widetilde{A}}(n)=\varepsilon _{A_N}(n')/3$, where $n'=2\mu$, $\mu =O(n)$ is the number of cycles in the optimal cycle cover $C^*$.

Now we can extend the structural results from the Corollary 1 to the case of an arbitrary normed space.

Corollary 3

Let $M^*$ be the maximum weight perfect matching, $C^*$ be the maximum weight cycle cover, and $H^*$ be the maximum weight Hamiltonian cycle of a complete graph G(V, E) in an arbitrary normed space of fixed dimension. Then the weights of the optimal $C^*,H^*$ and the doubled weight of $M^*$ are asymptotically equal: $2W(M^*) = W(H^*)(1+o(1)) = W(C^*)(1 + o(1))$.

4 Conclusion

This paper present a new modification $\widetilde{A}$ of an approximation algorithm for the Max TSP with $O(n^3)$ running-time. Maximum weight cycle cover $C^*$ of the initial graph is used as a foundation for constructing the approximate solutions. It is shown that if the number of cycles in $C^*$ is $\mu =o(n)$, algorithm $\widetilde{A}$ is asymptotically optimal for the Metric Max TSP (and, thus, also for the Euclidean Max TSP). In the case of $\mu =O(n)$ algorithm $\widetilde{A}$ is asymptotically optimal for the Euclidean Max TSP and due to [13] can be easily modified to give asymptotically optimal solutions for the Max TSP in an arbitrary normed space. The performance and analysis of algorithm $\widetilde{A}$ do not depend neither on the parity of the number of vertices in the initial graph, nor on the parity of the number of edges $\mu$ in the maximum weight matching.

As a corollary, we’ve showed that, given a complete undirected weighted graph in an arbitrary normed space, the weights of the maximum Hamiltonian cycle, the maximum weight cycle cover and the doubled weight of the maximum weight matching are asymptotically equal.

For the future work it would be interesting to extend the ideas of the algorithm, so it could find approximate solutions with improved approximation ratio for the Metric Max TSP, when $\mu =O(n)$.