{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:05Z","timestamp":1740109325476,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:00:00Z","timestamp":1693008000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:00:00Z","timestamp":1693008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["613.001.402"],"award-info":[{"award-number":["613.001.402"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, \u201cbeyond worst-case analysis\u201d of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erd\u0151s\u2013R\u00e9nyi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with \u2018fast growing cut sizes\u2019, i.e.\u00a0graphs for which <jats:inline-formula><jats:alternatives><jats:tex-math>$$|\\delta (U)|=\\Omega (|U|^\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>U<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>U<\/mml:mi>\n                    <mml:msup>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>\u03b5<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some constant <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon \\in (0,1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all subsets <jats:italic>U<\/jats:italic> of the vertices, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta (U)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>U<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the set of edges connecting <jats:italic>U<\/jats:italic> to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio.<\/jats:p>","DOI":"10.1007\/s00453-023-01167-3","type":"journal-article","created":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T06:01:56Z","timestamp":1693029716000},"page":"3793-3815","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics"],"prefix":"10.1007","volume":"85","author":[{"given":"Stefan","family":"Klootwijk","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6278-5059","authenticated-orcid":false,"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,26]]},"reference":[{"key":"1167_CR1","unstructured":"Auffinger, A., Damron, M., Hanson, J.: 50 years of first passage percolation. In: arXiv e-prints, arXiv:1511.03262 [math.PR] (2015)"},{"issue":"3","key":"1167_CR2","doi-asserted-by":"publisher","first-page":"723","DOI":"10.2307\/3213876","volume":"22","author":"T Aven","year":"1985","unstructured":"Aven, T.: Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables. J. Appl. Probab. 22(3), 723\u2013728 (1985). https:\/\/doi.org\/10.2307\/3213876","journal-title":"J. Appl. Probab."},{"issue":"2","key":"1167_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1017\/S0269964800000711","volume":"2","author":"D Avis","year":"1988","unstructured":"Avis, D., Davis, B., Steele, J.M.: Probabilistic analysis of a Greedy Heuristic for Euclidean matching. Probab. Eng. Inf. Sci. 2(2), 143\u2013156 (1988). https:\/\/doi.org\/10.1017\/S0269964800000711","journal-title":"Probab. Eng. Inf. Sci."},{"issue":"2","key":"1167_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0304-3975(94)90257-7","volume":"125","author":"V Bafna","year":"1994","unstructured":"Bafna, V., Kalyanasundaram, B., Pruhs, K.: Not all insertion methods yields constant approximate tours in the Euclidean plane. Theor. Comput. Sci. 125(2), 345\u2013353 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90257-7","journal-title":"Theor. Comput. Sci."},{"key":"1167_CR5","unstructured":"Bentley, J. L., Saxe, J.B.: An analysis of two Heuristics for the Euclidean traveling salesman problem. In: Proceedings of the Eighteenth Annual Allerton Conference on Communication, Control, and Computing, October 8\u201310, 1980. Allerton House, Monticello, Illinois (1980) pp. 41\u201349"},{"issue":"4","key":"1167_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/BF01275667","volume":"11","author":"B Bollob\u00e1s","year":"1991","unstructured":"Bollob\u00e1s, B., Leader, I.: Edge-isoperimetric inequalities in the grid. Combinatorica 11(4), 299\u2013314 (1991). https:\/\/doi.org\/10.1007\/BF01275667","journal-title":"Combinatorica"},{"issue":"2","key":"1167_CR7","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1023\/A:1009605613222","volume":"5","author":"J-L Bon","year":"1999","unstructured":"Bon, J.-L., P\u0103lt\u0103nea, E.: Ordering properties of convolutions of exponential random variables. Lifetime Data Anal. 5(2), 185\u2013192 (1999). https:\/\/doi.org\/10.1023\/A:1009605613222","journal-title":"Lifetime Data Anal."},{"issue":"1","key":"1167_CR8","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/s00453-014-9901-9","volume":"73","author":"K Bringmann","year":"2015","unstructured":"Bringmann, K., Engels, C., Manthey, B., Rao, B.V.R.: random shortest paths: non-Euclidean instances for metric optimization problems. Algorithmica 73(1), 42\u201362 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9901-9","journal-title":"Algorithmica"},{"issue":"6","key":"1167_CR9","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H., Tovey, C.: New results on the old k-opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6), 1998\u20132029 (1999). https:\/\/doi.org\/10.1137\/S0097539793251244","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1167_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(93)90059-I","volume":"46","author":"R Davis","year":"1993","unstructured":"Davis, R., Prieditis, A.: The expected length of a shortest path. Inf. Process. Lett. 46(3), 135\u2013141 (1993). https:\/\/doi.org\/10.1016\/0020-0190(93)90059-I","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1167_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.orl.2008.12.002","volume":"37","author":"C Engels","year":"2009","unstructured":"Engels, C., Manthey, B.: Average-case approximation ratio of the 2-opt algorithm for the TSP. Oper. Res. Lett. 37(2), 83\u201384 (2009). https:\/\/doi.org\/10.1016\/j.orl.2008.12.002","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1167_CR12","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s00453-013-9801-4","volume":"68","author":"M Englert","year":"2014","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68(1), 190\u2013264 (2014). https:\/\/doi.org\/10.1007\/s00453-013-9801-4","journal-title":"Algorithmica"},{"issue":"4","key":"1167_CR13","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1287\/moor.1040.0105","volume":"29","author":"AM Frieze","year":"2004","unstructured":"Frieze, A.M.: On random symmetric travelling salesman problems. Math. Oper. Res. 29(4), 878\u2013890 (2004). https:\/\/doi.org\/10.1287\/moor.1040.0105","journal-title":"Math. Oper. Res."},{"key":"1167_CR14","doi-asserted-by":"publisher","unstructured":"Frieze, A. M., Yukich, J. E.: Probabilistic analysis of the TSP. In: Gutin, G. and Punnen, A. P. (eds) The Traveling Salesman Problem and Its Variations. Springer, Boston, MA, Chap. 7, pp. 257\u2013307 (2007) https:\/\/doi.org\/10.1007\/0-306-48213-4_7","DOI":"10.1007\/0-306-48213-4_7"},{"key":"1167_CR15","doi-asserted-by":"publisher","unstructured":"Hammersley, J. M., Welsh, D. J. A.: First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In: Neyman, J. and Le Cam, L. M. (eds) Bernoulli 1713 Bayes 1763 Laplace 1813, Anniversary Volume, Proceedings of an International Research Seminar Statistical Laboratory, University of California, Berkeley 1963. Springer Berlin Heidelberg, pp. 61\u2013110 (1965) https:\/\/doi.org\/10.1007\/978-3-642-49750-6_7","DOI":"10.1007\/978-3-642-49750-6_7"},{"issue":"4","key":"1167_CR16","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1287\/moor.10.4.557","volume":"10","author":"R Hassin","year":"1985","unstructured":"Hassin, R., Zemel, E.: On shortest paths in graphs with random weights. Math. Oper. Res. 10(4), 557\u2013564 (1985). https:\/\/doi.org\/10.1287\/moor.10.4.557","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1167_CR17","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006). https:\/\/doi.org\/10.1090\/S0273-0979-06-01126-8","journal-title":"Bull. Am. Math. Soc."},{"key":"1167_CR18","doi-asserted-by":"publisher","unstructured":"Howard, C. D.: Models of first-passage percolation. In: Kesten, H. (ed) Probability on Discrete Structures. Springer, Berlin Heidelberg, pp. 125\u2013173 (2004). https:\/\/doi.org\/10.1007\/978-3-662-09444-0_3","DOI":"10.1007\/978-3-662-09444-0_3"},{"issue":"4","key":"1167_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S Janson","year":"1999","unstructured":"Janson, S.: One, two and three times log n\/n for paths in a complete graph with random weights. Combinat. Probab. Comput. 8(4), 347\u2013361 (1999). https:\/\/doi.org\/10.1017\/S0963548399003892","journal-title":"Combinat. Probab. Comput."},{"key":"1167_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.spl.2017.11.017","volume":"135","author":"S Janson","year":"2018","unstructured":"Janson, S.: Tail bounds for sums of geometric and exponential variables. Stat. Probab. Lett. 135, 1\u20136 (2018). https:\/\/doi.org\/10.1016\/j.spl.2017.11.017","journal-title":"Stat. Probab. Lett."},{"key":"1167_CR21","unstructured":"Karp, R. M., Steele, J. M.: Probabilistic analysis of heuristics. In: Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B. (eds) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, pp. 181\u2013205 (1985)"},{"key":"1167_CR22","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.tcs.2021.03.016","volume":"866","author":"S Klootwijk","year":"2021","unstructured":"Klootwijk, S., Manthey, B., Visser, S.K.: Probabilistic analysis of optimization problems on generalized random shortest path metrics. Theoret. Comput. Sci. 866, 107\u2013122 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.03.016","journal-title":"Theoret. Comput. Sci."},{"key":"1167_CR23","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"key":"1167_CR24","doi-asserted-by":"publisher","unstructured":"Reinelt, G.: The Traveling Salesman: Computational Solutions for TSP Applications. Lecture Notes in Computer Science 840. Berlin, Heidelberg: Springer-Verlag (1994) https:\/\/doi.org\/10.1007\/3-540-48661-5","DOI":"10.1007\/3-540-48661-5"},{"issue":"4","key":"1167_CR25","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"EM Reingold","year":"1981","unstructured":"Reingold, E.M., Tarjan, R.E.: On a greedy heuristic for complete matching. SIAM J. Comput. 10(4), 676\u2013681 (1981). https:\/\/doi.org\/10.1137\/0210050","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1167_CR26","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0305004100077288","volume":"74","author":"D Richardson","year":"1973","unstructured":"Richardson, D.: Random growth in a tessellation. Math. Proc. Camb. Philos. Soc. 74(3), 515\u2013528 (1973). https:\/\/doi.org\/10.1017\/S0305004100077288","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"3","key":"1167_CR27","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M.: An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3), 563\u2013581 (1977). https:\/\/doi.org\/10.1137\/0206041","journal-title":"SIAM J. Comput."},{"key":"1167_CR28","volume-title":"Introduction to Probability Models","author":"SM Ross","year":"2010","unstructured":"Ross, S.M.: Introduction to Probability Models. Academic Press, Burlington, MA (2010)"},{"key":"1167_CR29","unstructured":"Slootbeek, J. J. A.: Average-Case Analysis of the 2-opt Heuristic for the TSP. Master Thesis. University of Twente (2017)"},{"issue":"3","key":"1167_CR30","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/0208036","volume":"8","author":"DW Walkup","year":"1979","unstructured":"Walkup, D.W.: On the expected value of a random assignment problem. SIAM J. Comput. 8(3), 440\u2013442 (1979). https:\/\/doi.org\/10.1137\/0208036","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01167-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01167-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01167-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T13:05:53Z","timestamp":1699621553000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01167-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,26]]},"references-count":30,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1167"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01167-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,8,26]]},"assertion":[{"value":"7 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We have no conflicts of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}