Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension. (English) Zbl 1497.90184
Summary: The maximum traveling salesman problem (Max TSP) consists of finding a Hamiltonian cycle with the maximum total weight of the edges in a given complete weighted graph. This problem is APX-hard in the general metric case but admits polynomial-time approximation schemes in the geometric setting, when the edge weights are induced by a vector norm in fixed-dimensional real space. We propose the first approximation scheme for Max TSP in an arbitrary metric space of fixed doubling dimension. The proposed algorithm implements an efficient PTAS which, for any fixed \(\varepsilon \in (0,1)\), computes a \((1-\varepsilon)\)-approximate solution of the problem in cubic time. Additionally, we suggest a cubic-time algorithm which finds asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45, 5, 753-782 (1998) · Zbl 1064.90566 · doi:10.1145/290179.290180 |
| [2] | Bartal, Y.; Gottlieb, L-A; Krauthgamer, R., The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme, SIAM J. Comput., 45, 4, 1563-1581 (2016) · Zbl 1350.68288 · doi:10.1137/130913328 |
| [3] | Barvinok, A.; Fekete, SP; Johnson, DS; Tamir, A.; Woeginger, GJ; Woodroofe, R., The geometric maximum traveling salesman problem, J. ACM, 50, 5, 641-664 (2003) · Zbl 1325.90074 · doi:10.1145/876638.876640 |
| [4] | Barvinok, AI; Gimadi, EK; Serdyukov, AI; Gutin, G.; Punnen, AP, The maximum traveling salesman problem, The traveling salesman problem and its applications, 585-608 (2002), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1113.90350 |
| [5] | Bellman, R., Dynamic programming treatment of the travelling salesman problem, J. ACM, 9, 1, 61-63 (1962) · Zbl 0106.14102 · doi:10.1145/321105.321111 |
| [6] | Engebretsen, L.; Karpinski, M., TSP with bounded metrics, J. Comp. Syst. Sci., 72, 4, 509-546 (2006) · Zbl 1125.90066 · doi:10.1016/j.jcss.2005.12.001 |
| [7] | Fekete, S.P.: Simplicity and hardness of the maximum traveling salesman problem under geometric distances. In: Proceedings 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 337-345 (2015) · Zbl 0944.90104 |
| [8] | Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings 15th ACM Symposium on Theory of Computing (STOC 1983), pp. 448-456 (1983) |
| [9] | Held, M.; Karp, RM, A dynamic programming approach to sequencing problems, J. Soc. Indust. Appl. Math., 10, 1, 196-210 (1962) · Zbl 0106.14103 · doi:10.1137/0110015 |
| [10] | Kaplan, H.; Lewenstein, M.; Shafrir, N.; Sviridenko, M., Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs, J. ACM, 52, 4, 602-626 (2005) · Zbl 1323.68572 · doi:10.1145/1082036.1082041 |
| [11] | Kostochka, AV; Serdyukov, AI, Polynomial algorithms with the estimates \(3/4\) and \(5/6\) for the traveling salesman problem of the maximum (in Russian), Upravlyaemye Sistemy, 26, 55-59 (1985) |
| [12] | Kowalik, L.; Mucha, M., Deterministic \(7/8\)-approximation for the metric maximum TSP, Theor. Comp. Sci., 410, 47-49, 5000-5009 (2009) · Zbl 1209.90359 · doi:10.1016/j.tcs.2009.07.051 |
| [13] | Kowalik, L.; Mucha, M., \(35/44\)-approximation for asymmetric maximum TSP with triangle inequality, Algorithmica, 59, 2, 240-255 (2011) · Zbl 1206.68367 · doi:10.1007/s00453-009-9306-3 |
| [14] | Mitchell, JSB, Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, \(k\)-MST, and related problems, SIAM J. Comput., 28, 4, 1298-1309 (1999) · Zbl 0940.68062 · doi:10.1137/S0097539796309764 |
| [15] | Paluch, K., Mucha, M., Ma̧dry, A.: A \(7/9\)-approximation algorithm for the maximum traveling salesman problem. In: Proceedings 12th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2009), Lecture Notes in Computer Science, vol. 5687, 298-311 (2009) · Zbl 1255.68309 |
| [16] | Papadimitriou, CH, The Euclidean traveling salesman problem is NP-complete, Theor. Comp. Sci., 4, 3, 237-244 (1977) · Zbl 0386.90057 · doi:10.1016/0304-3975(77)90012-3 |
| [17] | Papadimitriou, CH; Yannakakis, M., The traveling salesman problem with distances one and two, Math. Oper. Res., 18, 1, 1-11 (1993) · Zbl 0778.90057 · doi:10.1287/moor.18.1.1 |
| [18] | Sahni, S.; Gonzalez, T., P-complete approximation problems, J. ACM, 23, 3, 555-565 (1976) · Zbl 0348.90152 · doi:10.1145/321958.321975 |
| [19] | Serdyukov, AI, An asymptotically exact algorithm for the traveling salesman problem for a maximum in Euclidean space (in Russian), Upravlyaemye sistemy, 27, 79-87 (1987) · Zbl 0654.90091 |
| [20] | Serdyukov, A.I.: Polynomial time algorithm with estimates of accuracy of solutions for one class of the maximum cost TSP (in Russian). In: Kombinatorno-Algebraicheskie Metody v Diskretnoi Optimizatsii, pp. 107-114. Nizhny Novgorod Univ., Nizhny Novgorod (1991) |
| [21] | Serdyukov, AI, The maximum-weight traveling salesman problem in finite-dimensional real spaces, Operations research and discrete analysis. Mathematics and its applications, 233-239 (1997), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0857.00023 |
| [22] | Shenmaier, VV, An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space, J. Appl. Industr. Math., 5, 2, 296-300 (2011) · doi:10.1134/S1990478911020177 |
| [23] | Shenmaier, VV, Asymptotically optimal algorithms for geometric Max TSP and Max \(m\)-PSP, Discrete Appl. Math., 163, 2, 214-219 (2014) · Zbl 1282.05205 · doi:10.1016/j.dam.2012.09.007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
