Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem

References

• [1] Afrati F, Cosmadakis S, Papadimitriou CH, Papageorgiou G, Papakostantinou N (1986) The complexity of the travelling repairman problem. RAIRO Theoretical Informatics Appl. 20(1):79–87.Crossref, Google Scholar
• [2] Arora S, Karakostas G (2006) A 2 + ε approximation algorithm for the k-MST problem. Math. Programming 107(3):491–504.Crossref, Google Scholar
• [3] 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
• [4] Ausiello G, Leonardi S, Marchetti-Spaccamela A (2000) On salesmen, repairmen, spiders, and other traveling agents. Bongiovanni G, Gambosi G, Petreschi R, eds. Italian Conf. Algorithms Complexity (Springer), 1–16.Google Scholar
• [5] Banerjee D, Erera AL, Toriello A (2023) Fleet sizing and service region partitioning for same-day delivery systems. Transportation Sci. 56(5):1327–1347.Link, Google Scholar
• [6] Banerjee D, Erera AL, Stroh AM, Toriello A (2022) Who has access to e-commerce and when? Time-varying service regions in same-day delivery. Transportation Res. Part B: Methodological 170:148–168.Google Scholar
• [7] Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Math. Proc. Cambridge Philos. Soc. 55(4):299–327.Crossref, Google Scholar
• [8] Bertsimas D, Gupta S (2016) Fairness and collaboration in network air traffic flow management: An optimization approach. Transportation Sci. 50(1):57–76.Google Scholar
• [9] Bertsimas D, Farias V, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• [10] Bertsimas D, Farias VF, Trichakis N (2012) On the efficiency-fairness trade-off. Management Sci. 58(12):2234–2250.Link, Google Scholar
• [11] Bertsimas DJ, Jaillet P, Odoni AR (1990) A priori optimization. Oper. Res. 38(6):1019–1033.Link, Google Scholar
• [12] Bianco L, Mingozzi A, Ricciardelli S (1993) The traveling salesman problem with cumulative costs. Networks 23(2):81–91.Crossref, Google Scholar
• [13] Blanchard M, Jacquillat A, Jaillet P (2022) Additional results and extensions for the paper “Probabilistic bounds on the k-traveling salesman problem and the traveling repairman problem”. Preprint, submitted November 20, https://arxiv.org/abs/2211.11065.Google Scholar
• [14] Blum A, Ravi R, Vempala S (1996) A constant-factor approximation algorithm for the k-MST problem. Miller GL, ed. Proc. 28th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 442–448.Google Scholar
• [15] Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. Leighton T, Goodrich M, eds. Proc. 26th Annual ACM Sympos. Theory Comput., 163–171.Google Scholar
• [16] Carlsson JG (2012) Dividing a territory among several vehicles. INFORMS J. Comput. 24(4):565–577.Link, Google Scholar
• [17] Carlsson JG, Jones B (2022) Continuous approximation formulas for location problems. Networks 80(4):407–430.Crossref, Google Scholar
• [18] Carlsson JG, Song S (2018) Coordinated logistics with a truck and a drone. Management Sci. 64(9):4052–4069.Link, Google Scholar
• [19] Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. Sudan M, eds. 44th Annual IEEE Sympos. Foundations Comput. Sci. Proc. (IEEE, Piscataway, NJ), 36–45.Google Scholar
• [20] Fischetti M, Hamacher HW, Jørnsten K, Maffioli F (1994) Weighted k-cardinality trees: Complexity and polyhedral structure. Networks 24(1):11–21.Crossref, Google Scholar
• [21] Garg N (1996) A 3-approximation for the minimum tree spanning k vertices. Raghavan P, eds. Proc. 37th Conf. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 302–309.Google Scholar
• [22] Garg N (2005) Saving an epsilon: A 2-approximation for the k-MST problem in graphs. Gabow H, Fafin R, eds. Proc. 37th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 396–402.Google Scholar
• [23] Goemans M, Kleinberg J (1998) An improved approximation ratio for the minimum latency problem. Math. Programming 82(1):111–124.Crossref, Google Scholar
• [24] Jacquillat A, Vaze V (2018) Interairline equity in airport scheduling interventions. Transportation Sci. 52(4):941–964.Link, Google Scholar
• [25] Jaillet P (1993) Analysis of probabilistic combinatorial optimization problems in Euclidean spaces. Math. Oper. Res. 18(1):51–70.Link, Google Scholar
• [26] Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: Theory and practice. Shmoys D, ed. Proc. 11th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 760–769.Google Scholar
• [27] Laporte G, Louveaux FV, Mercure H (1994) A priori optimization of the probabilistic traveling salesman problem. Oper. Res. 42(3):543–549.Link, Google Scholar
• [28] Luo H, Lu S, Bharghavan V, Cheng J, Zhong G (2004) A packet scheduling approach to QOS support in multihop wireless networks. Mobile Networks Appl. 9(3):193–206.Crossref, Google Scholar
• [29] Mallows C (1968) An inequality involving multinomial probabilities. Biometrika 55(2):422–424.Crossref, Google Scholar
• [30] Minieka E (1989) The delivery man problem on a tree network. Ann. Oper. Res. 18(1):261–266.Crossref, Google Scholar
• [31] Navidi F, Gørtz IL, Nagarajan V (2020) Approximation algorithms for the a priori traveling repairman. Oper. Res. Lett. 48(5):599–606.Crossref, Google Scholar
• [32] O’Cinneide C, Scherer B, Xu X (2006) Pooling trades in a quantitative investment process. J. Portfolio Management 32(4):33–43.Crossref, Google Scholar
• [33] Pandiri V, Singh A (2020) Two multi-start heuristics for the k-traveling salesman problem. Opsearch 57(4):1164–1204.Crossref, Google Scholar
• [34] Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576–590.Link, Google Scholar
• [35] Picard JC, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26(1):86–110.Link, Google Scholar
• [36] Radunovic B, Le Boudec JY (2007) A unified framework for max-min and min-max fairness with applications. IEEE/ACM Trans. Networking 15(5):1073–1083.Crossref, Google Scholar
• [37] Ravi R, Sundaram R, Marathe MV, Rosenkrantz DJ, Ravi SS (1996) Spanning trees—Short or small. SIAM J. Discrete Math. 9(2):178–200.Crossref, Google Scholar
• [38] Simchi-Levi D, Berman O (1991) Minimizing the total flow time of n jobs on a network. IIE Trans. 23(3):236–244.Crossref, Google Scholar
• [39] Sitters R (2002) The minimum latency problem is NP-hard for weighted trees. Cook WJ, Schulz AS, eds. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 230–239.Google Scholar
• [40] Sitters R (2014) Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 604–616.Google Scholar
• [41] Steele JM (1981) Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab. 9(3):365–376.Crossref, Google Scholar
• [42] Steele JM (1997) Probability Theory and Combinatorial Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [43] Stroh AM, Erera AL, Toriello A (2022) Tactical design of same-day delivery systems. Management Sci. 68(5):3444–3463.Link, Google Scholar
• [44] Tsitsiklis JN (1992) Special cases of traveling salesman and repairman problems with time windows. Networks 22(3):263–282.Crossref, Google Scholar
• [45] van Ee M, Sitters R (2018) The a priori traveling repairman problem. Algorithmica 80(10):2818–2833.Crossref, Google Scholar
• [46] Vossen T, Ball M, Hoffman R, Wambsganss M (2003) A general approach to equity in traffic flow management and its application to mitigating exemption bias in ground delay programs. Air Traffic Control Quart. 11(4):277–292.Crossref, Google Scholar