{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:30Z","timestamp":1759638990964},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,6,19]],"date-time":"2014-06-19T00:00:00Z","timestamp":1403136000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00453-014-9901-9","type":"journal-article","created":{"date-parts":[[2014,6,19]],"date-time":"2014-06-19T08:27:26Z","timestamp":1403166446000},"page":"42-62","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems"],"prefix":"10.1007","volume":"73","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[]},{"given":"Christian","family":"Engels","sequence":"additional","affiliation":[]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,19]]},"reference":[{"issue":"1","key":"9901_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0963548309990204","volume":"19","author":"L Addario-Berry","year":"2010","unstructured":"Addario-Berry, L., Broutin, N., Lugosi, G.: The longest minimum-weight path in a complete graph. Comb. Probab. Comput. 19(1), 1\u201319 (2010)","journal-title":"Comb. Probab. Comput."},{"key":"9901_CR2","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the $$k$$ k -means method. J. ACM 58(5), 19 (2011)","DOI":"10.1145\/2027216.2027217"},{"issue":"3","key":"9901_CR3","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for $$k$$ k -median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"9901_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, London (1999)"},{"key":"9901_CR5","doi-asserted-by":"crossref","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, 143\u2013156 (1988)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9901_CR6","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1017\/S096354830000119X","volume":"3","author":"Y Azar","year":"1994","unstructured":"Azar, Y.: Lower bounds for insertion methods for TSP. Comb. Probab. Comput. 3, 285\u2013292 (1994)","journal-title":"Comb. Probab. Comput."},{"issue":"5","key":"9901_CR7","doi-asserted-by":"crossref","first-page":"1907","DOI":"10.1214\/09-AAP666","volume":"20","author":"S Bhamidi","year":"2010","unstructured":"Bhamidi, S., van der Hofstad, R., Hooghiemstra, G.: First passage percolation on random graphs with finite mean degrees. Ann. Appl. Probab. 20(5), 1907\u20131965 (2010)","journal-title":"Ann. Appl. Probab."},{"issue":"5","key":"9901_CR8","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1017\/S096354831100023X","volume":"20","author":"S Bhamidi","year":"2011","unstructured":"Bhamidi, S., van der Hofstad, R., Hooghiemstra, G.: First passage percolation on the Erd\u0151s-R\u00e9nyi random graph. Combi. Probab. Comput. 20(5), 683\u2013707 (2011)","journal-title":"Combi. Probab. Comput."},{"key":"9901_CR9","unstructured":"Bhamidi, S., van der Hofstad, R., Hooghiemstra, G.: Universality for first passage percolation on sparse random graphs. Technical Report, arxiv.org\/pdf\/1005.0649 (2012)"},{"key":"9901_CR10","unstructured":"Blair-Stahn, N.D.: First passage percolation and competition models. Technical Report, arxiv.org\/pdf\/1005.0649v1 (2010)"},{"key":"9901_CR11","doi-asserted-by":"crossref","unstructured":"Broadbent, S.R., Hammersley, J.M.: Percolation processes. I. Crystals and mazes. In: Proceedings of the Cambridge Philosophical Society, vol. 53, Issue 3, pp. 629\u2013641 (1957)","DOI":"10.1017\/S0305004100032680"},{"issue":"6","key":"9901_CR12","doi-asserted-by":"crossref","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H.J., Tovey, C.A.: New results on the old $$k$$ k -opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9901_CR13","doi-asserted-by":"crossref","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)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9901_CR14","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1214\/aoap\/1177005436","volume":"3","author":"M Dyer","year":"1993","unstructured":"Dyer, M., Frieze, A., Pittel, B.: The average performance of the greedy matching algorithm. Ann. Appl. Probab. 3(2), 526\u2013552 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"9901_CR15","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF01585751","volume":"46","author":"ME Dyer","year":"1990","unstructured":"Dyer, M.E., Frieze, A.M.: On patching algorithms for random asymmetric travelling salesman problems. Math. Program. 46, 361\u2013378 (1990)","journal-title":"Math. Program."},{"issue":"6","key":"9901_CR16","doi-asserted-by":"crossref","first-page":"1056","DOI":"10.1007\/s10955-013-0743-7","volume":"151","author":"M Eckhoff","year":"2013","unstructured":"Eckhoff, M., Goodman, J., van der Hofstad, R., Nardi, F.R.: Short paths for first passage percolation on the complete graph. J. Stat. Phys. 151(6), 1056\u20131088 (2013)","journal-title":"J. Stat. Phys."},{"issue":"2","key":"9901_CR17","doi-asserted-by":"crossref","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)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9901_CR18","doi-asserted-by":"crossref","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)","journal-title":"Algorithmica"},{"issue":"4","key":"9901_CR19","doi-asserted-by":"crossref","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)","journal-title":"Math. Oper. Res."},{"key":"9901_CR20","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"AM Frieze","year":"1985","unstructured":"Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discret. Appl. Math. 10, 57\u201377 (1985)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"9901_CR21","doi-asserted-by":"crossref","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)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9901_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/S026996480115206X","volume":"15","author":"R Hofstad van der","year":"2001","unstructured":"van der Hofstad, R., Hooghiemstra, G., van Mieghem, P.: First passage percolation on the random graph. Probab. Eng. Inf. Sci. 15(2), 225\u2013237 (2001)","journal-title":"Probab. Eng. Inf. Sci."},{"issue":"6","key":"9901_CR23","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1017\/S0963548306007802","volume":"15","author":"R Hofstad van der","year":"2006","unstructured":"van der Hofstad, R., Hooghiemstra, G., van Mieghem, P.: Size and weight of shortest path trees with exponential link weights. Comb. Probab. Computi. 15(6), 903\u2013926 (2006)","journal-title":"Comb. Probab. Computi."},{"issue":"4","key":"9901_CR24","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S Janson","year":"1999","unstructured":"Janson, S.: One, two, three times $$\\log n\/n$$ log n \/ n for paths in a complete graph with edge weights. Comb. Probab. Comput. 8(4), 347\u2013361 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"9901_CR25","volume-title":"The Traveling Salesman Problem and its Variations, chap. 9","author":"DS Johnson","year":"2002","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variations, chap. 9. Kluwer, Dordrecht (2002)"},{"issue":"3","key":"9901_CR26","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"RM Karp","year":"1977","unstructured":"Karp, R.M.: Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res. 2(3), 209\u2013224 (1977)","journal-title":"Math. Oper. Res."},{"key":"9901_CR27","first-page":"181","volume-title":"The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization","author":"BM Karp","year":"1985","unstructured":"Karp, B.M., Steele, J.M.: Probabilistic analysis of heuristics. In: Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B. (eds.) The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization, pp. 181\u2013205. Wiley, Chichester (1985)"},{"issue":"2","key":"9901_CR28","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01587089","volume":"44","author":"W Kern","year":"1989","unstructured":"Kern, W.: A probabilistic analysis of the switching algorithm for the TSP. Math. Program. 44(2), 213\u2013219 (1989)","journal-title":"Math. Program."},{"key":"9901_CR29","unstructured":"Kolossv\u00e1ry, I., Komj\u00e1thy, J.: First passage percolation on inhomogeneous random graphs. Technical Report], arxiv.org\/pdf\/1201.3137v1 (2012)"},{"issue":"3","key":"9901_CR30","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1080\/15326348508807015","volume":"1","author":"VG Kulkarni","year":"1985","unstructured":"Kulkarni, V.G., Adlakha, V.G.: Maximum flow in planar networks in exponentially distributed arc capacities. Commun. Stat. Stoch. Models 1(3), 263\u2013289 (1985)","journal-title":"Commun. Stat. Stoch. Models"},{"issue":"3","key":"9901_CR31","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1002\/net.3230160303","volume":"16","author":"VG Kulkarni","year":"1986","unstructured":"Kulkarni, V.G.: Shortest paths in networks with exponentially distributed arc lengths. Networks 16(3), 255\u2013274 (1986)","journal-title":"Networks"},{"issue":"2","key":"9901_CR32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1002\/net.3230180204","volume":"18","author":"VG Kulkarni","year":"1988","unstructured":"Kulkarni, V.G.: Minimal spanning trees in undirected networks with exponentially distributed arc weights. Networks 18(2), 111\u2013124 (1988)","journal-title":"Networks"},{"key":"9901_CR33","doi-asserted-by":"crossref","unstructured":"Manthey, B., Veenstra, R.: Smoothed analysis of the 2-Opt heuristic for the TSP: Polynomial bounds for Gaussian noise. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 8283, pp. 579\u2013589. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-45030-3_54"},{"issue":"4","key":"9901_CR34","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2508028.2505988","volume":"60","author":"Y Peres","year":"2013","unstructured":"Peres, Y., Sotnikov, D., Sudakov, B., Zwick, U.: All-pairs shortest paths in $$O(n^2)$$ O ( n 2 ) time with high probability. J. ACM 60(4), 26 (2013)","journal-title":"J. ACM"},{"issue":"4","key":"9901_CR35","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9901_CR36","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"key":"9901_CR37","volume-title":"Introduction to Probability Models","author":"SM Ross","year":"2010","unstructured":"Ross, S.M.: Introduction to Probability Models, 10th edn. Academic Press, Burlington (2010)","edition":"10"},{"key":"9901_CR38","doi-asserted-by":"crossref","unstructured":"Supowit, K.J., Plaisted, D.A., Reingold, E.M.: Heuristics for weighted perfect matching. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 398\u2013419. ACM (1980)","DOI":"10.1145\/800141.804689"},{"issue":"2","key":"9901_CR39","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1070\/RM2004v059n02ABEH000718","volume":"59","author":"AM Vershik","year":"2004","unstructured":"Vershik, A.M.: Random metric spaces and universality. Russian Math. Surv. 59(2), 259\u2013295 (2004)","journal-title":"Russian Math. Surv."},{"key":"9901_CR40","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability Theory of classical euclidean optimization problems. Lecture Notes in Mathematics, vol. 1675. Springer, Heidelberg (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9901-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9901-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9901-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T14:28:38Z","timestamp":1565533718000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9901-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,19]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9901"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9901-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,19]]}}}