Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem
Ksenia  Ryzhenko, Katherine  Neznakhina, Michael  Khachay

References
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
2.	Balas E., “The prize collecting traveling salesman problem”, Networks, 19:6 (1989), 621–636
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
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
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
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
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
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
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
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
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
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
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
14.	Feillet D., Dejax P., Gendreau M., “Traveling salesman problems with profits”, Transport. Sci., 39:2 (2005), 188–205
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
16.	Goemans M. X., Williamson D. P., “A general approximation technique for constrained forest problems”, SIAM J. Comput., 24:2 (1995), 296–317
17.	Gutin G., Punnen A.P., The Traveling Salesman Problem and Its Variations, Boston, MA, 2007, 38 pp.
18.	Jackson B., “Some remarks on Arc-connectivity, vertex splitting, and orientation in graphs and digraphs”, J. Graph Theory, 12:3 (1988), 429–436
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
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
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
22.	Lovász L., “On some connectivity properties of {E}ulerian graphs”, Acta Math. Acad. Scientiarum Hungarica, 28:1 (1976), 129–138
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
24.	Nguyen V. H., Nguyen T. T. T., “Approximating the asymmetric profitable tour”, Electron. Notes Discrete Math., 36 (2010), 907–914
25.	Papadimitriou C., “The Euclidean travelling salesman problem is NP-complete”, Theoret. Comput. Sci., 4:3 (1977), 237–244
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
27.	Sahni S., “$P$-complete approximation problems”, J. ACM, 23:3 (1976), 555–565
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
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
30.	Vansteenwegen P., Gunawan A., Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits, Springer, Cham, 2019, 112 pp.