FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM

Ksenia Rizhenko     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108, Russian Federation)
Katherine Neznakhina     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108, Russian Federation)
Michael Khachay     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108, Russian Federation)

Abstract


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.


Keywords


Prize-Collecting Traveling Salesman Problem, Triangle inequality, Approximation algorithm, Fixed approximation ratio.

Full Text:

PDF

References


  1. Archer A., Bateni M., Hajiaghayi M., Karloff H. Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput., 2011. Vol. 40, No. 2. P. 309–332. DOI: 10.1137/090771429
  2. Balas E. The prize collecting traveling salesman problem. Networks, 1989. Vol. 19, No. 6. P. 621–636. DOI: 10.1002/net.3230190602
  3. Bartal Y., Gottlieb L.A., Krauthgamer R. The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 2016. Vol. 45, No. 4. P. 1563–1581. DOI: 10.1137/130913328
  4. Bateni M., Chekuri C., Ene A., Hajiaghayi M., Korula N., Marx D. Prize-collecting Steiner problems on planar graphs. In: Proc. 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. P. 1028–1049. DOI: 10.1137/1.9781611973082.79
  5. Bérubé J.F., Gendreau M., Potvin J.-Y. A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem. Networks, 2009. Vol. 54, No. 1. P. 56–67. DOI: 10.1002/net.20307
  6. Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D. A note on the prize collecting traveling salesman problem. Math. Program., 1993. Vol. 59. P. 413–420. DOI: 10.1007/BF01581256
  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. In: LIPIcs. Leibniz Int. Proc. Inform., vol. 112: 26th Annual European Symposium on Algorithms (ESA 2018), Y. Azar, H. Bast, G. Herman (eds.). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. Art. no. 15. P. 1–13. DOI: 10.4230/LIPIcs.ESA.2018.15
  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, 2018. Vol. 14, No. 1. Art. no. 9. P. 1–18. DOI: 10.1145/3158232
  9. Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. In: Abstr. Of Symposium on New Directions and Recent Results in Algorithms and Complexity, J.F.Traub (ed.). NY: Academic Press, 1976. P. 441.
  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., 2020. Vol. 123. P. 105004. DOI: 10.1016/j.cor.2020.105004
  11. Climaco G., Simonetti L., Rosetti I. A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem. RAIRO-Oper. Res., 2021. Vol. 55. P. S719–S726. DOI: 10.1051/ro/2020002
  12. Dell’Amico M., Maffioli F., Värbrand P. On prize-collecting tours and the asymmetric travelling  salesman problem. Int. Trans. Oper. Res., 1995. Vol. 2, No. 3. P. 297–308. DOI: 10.1016/0969-6016(95)00010-5
  13. Dogan O., Alkaya A.F. A novel method for prize collecting traveling salesman problem with time windows. In: Lect. Notes Networks Systems, vol 307: Intelligent and Fuzzy Techniques for Emerging Conditions and Digital Transformation, C. Kahraman at al.(eds.). Cham: Springer, 2022. P. 469–476. DOI: 10.1007/978-3-030-85626-7_55
  14. Feillet D., Dejax P., Gendreau M. Traveling salesman problems with profits. Transport. Sci., 2005. Vol. 39, No. 2. P. 188–205. DOI: 10.1287/trsc.1030.0079
  15. Fischetti M., Toth P. An additive approach for the optimal solution of the prize collecting traveling salesman problem. In: Vehicle Routing: Methods and Studies, B.L. Golden, A.A. Assad (eds.). North-Holland, 1988. P. 319–343.
  16. Goemans M.X., Williamson D.P. A general approximation technique for constrained forest problems. SIAM J. Comput., 1995. Vol. 24, No. 2. P. 296–317. DOI: 10.1137/S0097539793242618
  17. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Boston, MA: Springer US,  2007. 38 p.
  18. Jackson B. Some remarks on Arc-connectivity, vertex splitting, and orientation in graphs and digraphs. J. Graph Theory, 1988. Vol. 12, No. 3. P. 429–436. DOI: 10.1002/jgt.3190120314
  19. Khachay M., Ogorodnikov Y., Khachay D. Efficient approximation of the metric CVRP in spaces of fixed doubling dimension. J. Global Optim., 2021. Vol. 80. P. 679–710. DOI: 10.1007/s10898-020-00990-0
  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., 2023. Vol. 309, No. 2. P. 488–505. DOI: 10.1016/j.ejor.2023.01.039
  21. Lahyani R., Khemakhem M., Semet F. A unified matheuristic for solving multi-constrained traveling salesman problems with profits. EURO J. Comput. Optim., 2017. Vol. 5, No. 3. P. 393–422. DOI: 10.1007/s13675-016-0071-1
  22. Lovász L. On some connectivity properties of Eulerian graphs. Acta Math. Acad. Scientiarum Hungarica, 1976. Vol. 28, No. 1. P. 129–138. DOI: 10.1007/BF0190250
  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, 2020. Vol. 27, No. 2. P. 13–29. DOI: 10.22456/2175-2745.94082
  24. Nguyen V.H., Nguyen T.T.T. Approximating the asymmetric profitable tour. Electron. Notes Discrete Math., 2010. Vol. 36. P. 907–914. DOI: 10.1016/j.endm.2010.05.115
  25. Papadimitriou C. The Euclidean travelling salesman problem is NP-complete. Theoret. Comput. Sci., 1977. Vol. 4, No. 3. P. 237–244. DOI: 10.1016/0304-3975(77)90012-3
  26. Pedro O., Saldanha R., Camargo R. A tabu search approach for the prize collecting traveling salesman problem. Electron. Notes Discrete Math., 2013. Vol. 41. P. 261–268. DOI: 10.1016/j.endm.2013.05.101
  27. Sahni S. P-complete approximation problems. J. ACM, 1976. Vol. 23, No. 3. P. 555–565.
  28. Svensson O., Tarnawski J., Végh L.A. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In: Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). New York, USA: Association for Computing Machinery, 2018. P. 204–213. DOI: 10.1145/3188745.3188824
  29. Traub V., Vygen J. An improved approximation algorithm for ATSP. In: Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). New York, USA: Association for Computing Machinery, 2020. P. 1–13. DOI: 10.1145/3357713.3384233
  30. Vansteenwegen P., Gunawan A. Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits. Cham: Springer, 2019. 112 p. DOI: 10.1007/978-3-030-29746-6




DOI: http://dx.doi.org/10.15826/umj.2023.1.012

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.