Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems

References

• [1] Archer A, Bateni MH, Hajiaghayi MT, Karloff H (2011) Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40(2):309–332.Crossref, Google Scholar
• [2] Arya S, Ramesh H (1998) A 2.5-factor approximation algorithm for the k-MST problem. Inform. Processing Lett. 65(3):117–118.Crossref, Google Scholar
• [3] Ausiello G, Demange M, Laura L, Paschos V (2004) Algorithms for the on-line quota traveling salesman problem. Inform. Processing Lett. 92(2):89–94.Crossref, Google Scholar
• [4] Blum A, Ravi R, Vempala S (1996) A constant-factor approximation algorithm for the k-MST problem. Proc. 28th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 442–448.Google Scholar
• [5] Chekuri C, Pál M (2005) A recursive greedy algorithm for walks in directed graphs. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 245–253.Google Scholar
• [6] Chekuri C, Korula N, Pál M (2012) Improved algorithms for orienteering and related problems. ACM Trans. Algorithms 8(3):Article 23.Google Scholar
• [7] Chen K, Har-Peled S (2006) The orienteering problem in the plane revisited. Proc. 22nd Annual Sympos. Comput. Geometry (Association for Computing Machinery, New York), 247–254.Google Scholar
• [8] Dilkina B, Gomes C (2010) Solving connected subgraph problems in wildlife conservation. Lodi A, Milano M, Toth P, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, vol. 6140 (Springer, Berlin), 102–116.Google Scholar
• [9] Feigenbaum J, Papadimitriou CH, Shenker S (2001) Sharing the cost of multicast transmissions. J. Comput. System Sci. 63(1):21–41.Crossref, Google Scholar
• [10] Frederickson GN, Wittman B (2012) Approximation algorithms for the traveling repairman and speeding deliveryman problems. Algorithmica 62(3–4):1198–1221.Crossref, Google Scholar
• [11] Freund D, Norouzi-Fard A, Paul A, Henderson SG, Shmoys DB (2017) Data-driven rebalancing methods for bike-share systems. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar
• [12] Garg N (1996) A 3-approximation for the minimum tree spanning k vertices. Proc. 37th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 302–309.Google Scholar
• [13] Garg N (2005) Saving an epsilon: A 2-approximation for the k-MST problem in graphs. Proc. 37th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 396–402.Google Scholar
• [14] Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• [15] Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2012) Approximation algorithms for stochastic orienteering. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1522–1538.Google Scholar
• [16] Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: Theory and practice. Proc. 11th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 760–769.Google Scholar
• [17] Kaspi M, Raviv T, Tzur M (2016) Detection of unusable bicycles in bike-sharing systems. Omega 65(December):10–16.Crossref, Google Scholar
• [18] Levin A (2004) A better approximation algorithm for the budget prize collecting tree problem. Oper. Res. Lett. 32(4):316–319.Crossref, Google Scholar
• [19] Nagarajan V, Ravi R (2012) Approximation algorithms for distance constrained vehicle routing problems. Networks 59(2):209–214.Crossref, Google Scholar
• [20] Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• [21] Vidyarthi S, Shukla KK (2015) Approximation algorithms for P2P orienteering and stochastic vehicle routing problem. Working paper, Amazon, Seattle.Google Scholar