Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem

Ksenia Ryzhenko   ; Katherine Neznakhina   ; Michael Khachay

Ural mathematical journal, Tome 9 (2023) no. 1, pp. 135-146

Résumé

We develop the first fixed-ratio approximation algorithm for the well-known Prize-Collecting Asymmetric Traveling Salesman Problem, which has numerous valuable applications in operations research. An instance of this problem is given by a complete node- and edge-weighted digraph $G$. Each node of the graph $G$ can either be visited by the resulting route or skipped, for some penalty, while the arcs of $G$ are weighted by non-negative transportation costs that fulfill the triangle inequality constraint. The goal is to find a closed walk that minimizes the total transportation costs augmented by the accumulated penalties. We show that an arbitrary $\alpha$-approximation algorithm for the Asymmetric Traveling Salesman Problem induces an $(\alpha+1)$-approximation for the problem in question. In particular, using the recent $(22+\varepsilon)$-approximation algorithm of V. Traub and J. Vygen that improves the seminal result of O. Svensson, J. Tarnavski, and L. Végh, we obtain $(23+\varepsilon)$-approximate solutions for the problem.

Détail

Keywords: Prize-Collecting Traveling Salesman Problem, triangle inequality, approximation algorithm, fixed approximation ratio.

Bibliographie

[1] Archer A., Bateni M., Hajiaghayi M., Karloff H., “Improved approximation algorithms for prize-collecting Steiner tree and {TSP}”, SIAM J. Comput., 40:2 (2011), 309–332 | DOI | MR | Zbl

[2] Balas E., “The prize collecting traveling salesman problem”, Networks, 19:6 (1989), 621–636 | DOI | MR | Zbl

[3] Bartal Y., Gottlieb L. A., Krauthgamer R., “The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme”, SIAM J. Comput., 45 (2016), 1563–1581 | DOI | MR | Zbl

[4] Bateni M., Chekuri C., Ene A., Hajiaghayi M., Korula N., Marx D., “Prize-collecting Steiner problems on planar graphs”, Proc. 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011, 1028–1049 | DOI | MR | Zbl

[5] Bérubé J. F., Gendreau M., Potvin J.-Y., “A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem”, Networks, 54:1 (2009), 56–67 | DOI | MR

[6] Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D., “A note on the prize collecting traveling salesman problem”, Math. Program., 59 (1993), 413–420 | DOI | MR | Zbl

[7] Chan T.-H. H., Jiang H., Jiang S. H. C., “A unified {PTAS} for prize collecting {TSP} and Steiner tree problem in doubling metrics”, LIPIcs. Leibniz Int. Proc. Inform., 26th Annual European Symposium on Algorithms (ESA 2018), v. 112, eds. Y. Azar, H. Bast, G. Herman, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, 15, 1–13 | DOI | MR | Zbl

[8] Chan T.-H. H., Jiang S. H. C., “Reducing curse of dimensionality: improved {PTAS} for {TSP} (with neighborhoods) in doubling metrics”, ACM Trans. Algorithms, 14 (2018), 9, 1–18 | DOI | MR | Zbl

[9] Christofides N., “Worst-case analysis of a new heuristic for the traveling salesman problem”, Abstr. of Symposium on New Directions and Recent Results in Algorithms and Complexity, ed. J.F. Traub, Academic Press, NY, 1976, 441 | MR

[10] Chung S. H., Sah B., Lee J., “Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions”, Comput. Oper. Res., 123 (2020), 105004 | DOI | MR | Zbl

[11] Climaco G., Simonetti L., Rosetti I., “A {B}ranch-and-{C}ut and {MIP}-based heuristics for the {P}rize-{C}ollecting {T}ravelling {S}alesman {P}roblem”, RAIRO-Oper. Res., 55 (2021), S719–S726 | DOI | MR | Zbl

[12] Dell'Amico M., Maffioli F., Värbrand P., “On prize-collecting tours and the asymmetric travelling salesman problem”, Int. Trans. Oper. Res., 2:3 (1995), 297–308 | DOI | MR | Zbl

[13] Dogan O., Alkaya A. F., “A novel method for prize collecting traveling salesman problem with time windows”, Lect. Notes Networks Systems, Intelligent and Fuzzy Techniques for Emerging Conditions and Digital Transformation, v. 307, eds. C. Kahraman at al., Springer, Cham, 2022, 469–476 | DOI

[14] Feillet D., Dejax P., Gendreau M., “Traveling salesman problems with profits”, Transport. Sci., 39:2 (2005), 188–205 | DOI

[15] Fischetti M., Toth P., “An additive approach for the optimal solution of the prize collecting traveling salesman problem”, Vehicle Routing: Methods and Studies, eds. B.L. Golden, A.A. Assad, North-Holland, 1988, 319–343 | MR | Zbl

[16] Goemans M. X., Williamson D. P., “A general approximation technique for constrained forest problems”, SIAM J. Comput., 24:2 (1995), 296–317 | DOI | MR | Zbl

[17] Gutin G., Punnen A.P., The Traveling Salesman Problem and Its Variations, Boston, MA, 2007, 38 pp. | MR | Zbl

[18] Jackson B., “Some remarks on Arc-connectivity, vertex splitting, and orientation in graphs and digraphs”, J. Graph Theory, 12:3 (1988), 429–436 | DOI | MR | Zbl

[19] Khachay M., Ogorodnikov Y., Khachay D., “Efficient approximation of the metric {CVRP} in spaces of fixed doubling dimension”, J. Global Optim., 80 (2021), 679–710 | DOI | MR | Zbl

[20] Khachai D., Sadykov R., Battaia O., Khachay M., “Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm”, European J. Oper. Res., 309:2 (2023), 488–505 | DOI | MR

[21] Lahyani R., Khemakhem M., Semet F., “A unified matheuristic for solving multi-constrained traveling salesman problems with profits”, EURO J. Comput. Optim., 5:3 (2017), 393–422 | DOI | MR | Zbl

[22] Lovász L., “On some connectivity properties of {E}ulerian graphs”, Acta Math. Acad. Scientiarum Hungarica, 28:1 (1976), 129–138 | DOI | MR | Zbl

[23] de Medeiros Y. A., Goldbarg M. C., Goldbarg E. F. G., “Prize collecting traveling salesman problem with ridesharing”, Revista de Informática Teórica e Aplicada, 27:2 (2020), 13–29 | DOI

[24] Nguyen V. H., Nguyen T. T. T., “Approximating the asymmetric profitable tour”, Electron. Notes Discrete Math., 36 (2010), 907–914 | DOI | MR | Zbl

[25] Papadimitriou C., “The Euclidean travelling salesman problem is NP-complete”, Theoret. Comput. Sci., 4:3 (1977), 237–244 | DOI | MR | Zbl

[26] Pedro O., Saldanha R., Camargo R., “A tabu search approach for the prize collecting traveling salesman problem”, Electron. Notes Discrete Math., 41 (2013), 261–268 | DOI

[27] Sahni S., “$P$-complete approximation problems”, J. ACM, 23:3 (1976), 555–565 | MR | Zbl

[28] Svensson O., Tarnawski J., Végh L. A., “A constant-factor approximation algorithm for the asymmetric traveling salesman problem”, Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Association for Computing Machinery, New York, USA, 2018, 204–213 | DOI | MR | Zbl

[29] Traub V., Vygen J., “An improved approximation algorithm for ATSP”, Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Association for Computing Machinery, New York, USA, 2020, 1–13 | DOI | MR | Zbl

[30] Vansteenwegen P., Gunawan A., Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits, Springer, Cham, 2019, 112 pp. | DOI | MR