{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:38:28Z","timestamp":1758476308707},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_21","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"219-230","source":"Crossref","is-referenced-by-count":2,"title":["Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems"],"prefix":"10.1007","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Engels","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"21_CR1","doi-asserted-by":"publisher","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. Combin. Probab. Comput.\u00a019(1), 1\u201319 (2010)","journal-title":"Combin. Probab. Comput."},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"21_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. Engrg. Inform. Sci.\u00a02, 143\u2013156 (1988)","journal-title":"Probab. Engrg. Inform. Sci."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1017\/S096354830000119X","volume":"3","author":"Y. Azar","year":"1994","unstructured":"Azar, Y.: Lower bounds for insertion methods for TSP. Combin. Probab. Comput.\u00a03, 285\u2013292 (1994)","journal-title":"Combin. Probab. Comput."},{"issue":"5","key":"21_CR5","doi-asserted-by":"publisher","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. Combin. Probab. Comput.\u00a020(5), 683\u2013707 (2011)","journal-title":"Combin. Probab. Comput."},{"key":"21_CR6","unstructured":"Blair-Stahn, N.D.: First passage percolation and competition models. arXiv:1005.0649v1 [math.PR] (2010)"},{"issue":"3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1017\/S0305004100032680","volume":"53","author":"S.R. Broadbent","year":"1957","unstructured":"Broadbent, S.R., Hemmersley, J.M.: Percolation processes. I. Crystals and mazes. Proceedings of the Cambridge Philosophical Society\u00a053(3), 629\u2013641 (1957)","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"issue":"6","key":"21_CR8","doi-asserted-by":"publisher","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-opt algorithm for the traveling salesman problem. SIAM J. Comput.\u00a028(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"21_CR9","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. Inform. Process. Lett.\u00a046(3), 135\u2013141 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"21_CR10","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1214\/aoap\/1177005436","volume":"3","author":"M. Dyer","year":"1993","unstructured":"Dyer, M., Frieze, A.M., Pittel, B.: The average performance of the greedy matching algorithm. Ann. Appl. Probab.\u00a03(2), 526\u2013552 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF01585751","volume":"46","author":"M.E. Dyer","year":"1990","unstructured":"Dyer, M.E., Frieze, A.M.: On patching algorithms for random asymmetric travelling salesman problems. Math. Program.\u00a046, 361\u2013378 (1990)","journal-title":"Math. Program."},{"key":"21_CR12","unstructured":"Eckhoff, M., Goodman, J., van der Hofstad, R., Nardi, F.R.: Short paths for first passage percolation on complete graphs. arXiv:1211.4569v1 [math.PR] (2012)"},{"issue":"2","key":"21_CR13","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.\u00a037(2), 83\u201384 (2009)","journal-title":"Oper. Res. Lett."},{"key":"21_CR14","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proc. of the 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1295\u20131304. SIAM (2007)"},{"issue":"4","key":"21_CR15","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1287\/moor.1040.0105","volume":"29","author":"A.M. Frieze","year":"2004","unstructured":"Frieze, A.M.: On random symmetric travelling salesman problems. Math. Oper. Res.\u00a029(4), 878\u2013890 (2004)","journal-title":"Math. Oper. Res."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A.M. Frieze","year":"1985","unstructured":"Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math.\u00a010, 57\u201377 (1985)","journal-title":"Discrete Appl. Math."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci.\u00a038, 293\u2013306 (1985)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"21_CR18","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.\u00a010(4), 557\u2013564 (1985)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"21_CR19","doi-asserted-by":"publisher","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. Engrg. Inform. Sci.\u00a015(2), 225\u2013237 (2001)","journal-title":"Probab. Engrg. Inform. Sci."},{"issue":"6","key":"21_CR20","doi-asserted-by":"publisher","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. Combin. Probab. Comput.\u00a015(6), 903\u2013926 (2006)","journal-title":"Combin. Probab. Comput."},{"issue":"4","key":"21_CR21","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S. Janson","year":"1999","unstructured":"Janson, S.: One, two, three times logn\/n for paths in a complete graph with edge weights. Combin. Probab. Comput.\u00a08(4), 347\u2013361 (1999)","journal-title":"Combin. Probab. Comput."},{"key":"21_CR22","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. Kluwer (2002)"},{"issue":"3","key":"21_CR23","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"Karp, R.M.: Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res.\u00a02(3), 209\u2013224 (1977)","journal-title":"Math. Oper. Res."},{"key":"21_CR24","unstructured":"Karp, R.M., Steele, J.M.: Probabilistic analysis of heuristics. In: Lawler, E.L., et al. (eds.) The Traveling Salesman Problem, pp. 181\u2013205. Wiley (1985)"},{"issue":"3","key":"21_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1080\/15326348508807015","volume":"1","author":"V.G. Kulkarni","year":"1985","unstructured":"Kulkarni, V.G., Adlakha, V.G.: Maximum flow in planar networks in exponentially distributed arc capacities. Comm. Statist. Stochastic Models\u00a01(3), 263\u2013289 (1985)","journal-title":"Comm. Statist. Stochastic Models"},{"issue":"3","key":"21_CR26","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1002\/net.3230160303","volume":"16","author":"V.G. Kulkarni","year":"1986","unstructured":"Kulkarni, V.G.: Shortest paths in networks with exponentially distributed arc lengths. Networks\u00a016(3), 255\u2013274 (1986)","journal-title":"Networks"},{"issue":"2","key":"21_CR27","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/net.3230180204","volume":"18","author":"V.G. Kulkarni","year":"1988","unstructured":"Kulkarni, V.G.: Minimal spanning trees in undirected networks with exponentially distributed arc weights. Networks\u00a018(2), 111\u2013124 (1988)","journal-title":"Networks"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Peres, Y., Sotnikov, D., Sudakov, B., Zwick, U.: All-pairs shortest paths in o(n\n                        2) time with high probability. In: Proc. of the 51st Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 663\u2013672. IEEE (2010)","DOI":"10.1109\/FOCS.2010.69"},{"issue":"4","key":"21_CR29","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"E.M. Reingold","year":"1981","unstructured":"Reingold, E.M., Tarjan, R.E.: On a greedy heuristic for complete matching. SIAM J. Comput.\u00a010(4), 676\u2013681 (1981)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"21_CR30","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.J. 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.\u00a06(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Ross, S.M.: Introduction to Probability Models. Academic Press (2010)","DOI":"10.1016\/B978-0-12-375686-2.00007-8"},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"Supowit, K.J., Plaisted, D.A., Reingold, E.M.: Heuristics for weighted perfect matching. In: Proc. of the 12th Ann. ACM Symp. on Theory of Computing (STOC), pp. 398\u2013419. ACM (1980)","DOI":"10.1145\/800141.804689"},{"issue":"2","key":"21_CR33","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1070\/RM2004v059n02ABEH000718","volume":"59","author":"A.M. Vershik","year":"2004","unstructured":"Vershik, A.M.: Random metric spaces and universality. Russian Math. Surveys\u00a059(2), 259\u2013295 (2004)","journal-title":"Russian Math. Surveys"},{"issue":"3","key":"21_CR34","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/0208036","volume":"8","author":"D.W. Walkup","year":"1979","unstructured":"Walkup, D.W.: On the expected value of a random assignment problem. SIAM J. Comput.\u00a08(3), 440\u2013442 (1979)","journal-title":"SIAM J. Comput."},{"key":"21_CR35","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Springer (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:12:07Z","timestamp":1558303927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}