{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:30:32Z","timestamp":1760707832962},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_23","type":"book-chapter","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T22:58:05Z","timestamp":1181170685000},"page":"294-306","source":"Crossref","is-referenced-by-count":17,"title":["Random Geometric Problems on [0, 1]2"],"prefix":"10.1007","author":[{"given":"Josep","family":"D\u00edaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jordi","family":"Petit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Serna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1214\/aoap\/1177005773","volume":"2","author":"F. Avram","year":"1992","unstructured":"F. Avram and D. Bertsimas. The minimum spanning tree constant in geometric probability and under the independent model: A unified approach. The Annals of Applied Probability., 2:113\u2013130, 1992.","journal-title":"The Annals of Applied Probability"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1214\/aoap\/1177005271","volume":"3","author":"F. Avram","year":"1993","unstructured":"F. Avram and D. Bertsimas. On the central limit theorems in geometrical probability. The Annals of Applied Probability., 3:1033\u20131046, 1993.","journal-title":"The Annals of Applied Probability"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"567","DOI":"10.2307\/1428076","volume":"29","author":"M.J. Appel","year":"1997","unstructured":"M.J. Appel and R.P. Russo. The maximum vertex degree of a graph on uniform points in [0; 1]d. Adv. Applied Probability., 29:567\u2013581, 1997.","journal-title":"Adv. Applied Probability"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"582","DOI":"10.2307\/1428077","volume":"29","author":"M.J. Appel","year":"1997","unstructured":"M.J. Appel and R.P. Russo. The minimum vertex degree of a graph on uniform points in [0; 1]d. Adv. Applied Probability., 29:582\u2013594, 1997.","journal-title":"Adv. Applied Probability"},{"key":"23_CR5","volume-title":"The probabilistic method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J.H. Spencer, and P. Erd\u00f6s. The probabilistic method. Wiley-Interscience, New York, 1992."},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"J. Beardwood, J. Halton, and J.M. Hammersley. The shortest path through many points. Proceedings of the Cambridge Philos. Society., 55:299\u2013327, 1959.","journal-title":"Proceedings of the Cambridge Philos. Society"},{"key":"23_CR7","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas. Random Graphs. Academic Press, London, 1985."},{"key":"23_CR8","volume-title":"A course in Probability Theory","author":"K. Chung","year":"1974","unstructured":"K. Chung. A course in Probability Theory. Academic Press, New York, 1974."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.2307\/3214317","volume":"26","author":"H. Dette","year":"1989","unstructured":"H. Dette and N. Henze. The limit distribution of the largest nearest-neighbour link in the unit d-cube.. Journal Applied Probability., 26:67\u201380, 1989.","journal-title":"Journal Applied Probability"},{"key":"23_CR10","unstructured":"J. D\u00edaz, J. Petit i Silvestre, M. Serna, and P. Spirakis. Heuristics for the MinLA Problem: An Empirical and Theoretical Analysis. Technical Report LSI-98-42-R, Departament de Llenguatges i Sistemes Inform\u00e0tics, Universitat Polit\u00e9cnica de Catalunya, 1998."},{"key":"23_CR11","unstructured":"J. D\u00edaz, J. Petit, M. Serna, and L. Trevisan. Approximating layout problems on random sparse graphs. Technical Report LSI 98-44-R, Universitat Polit\u00e8cnica de Catalunya, 1998."},{"key":"23_CR12","first-page":"290","volume":"6","author":"P. Erdos","year":"1959","unstructured":"P. Erdos and A. Renyi. On random graphs-i. Publicationes Matematicae, 6:290\u2013297, 1959.","journal-title":"Publicationes Matematicae"},{"key":"23_CR13","first-page":"17","volume":"5","author":"P. Erdos","year":"1960","unstructured":"P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungarian Academy of Sciences., 5:17\u201361, 1960.","journal-title":"Publ. Math. Inst. Hungarian Academy of Sciences"},{"key":"23_CR14","unstructured":"A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. In 37th. FOCS, pages 62\u201371, 1996."},{"key":"23_CR15","unstructured":"A Frieze and C. McDiarmid. Algorithmic theory of random graph. Technical report, Department of Mathematics. Carnegie Mellon University., 1996."},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0211003","volume":"11","author":"J.H. Halton","year":"1982","unstructured":"J.H. Halton and R. Terada. A fast algorithm for the euclidian traveling-salesman problem, optimal with probability one. SIAM Journal on Computing, 11:28\u201346, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR17","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"R.M. Karp. Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plane. Mathematics of Operation Research., 2:209\u2013224, 1977.","journal-title":"Mathematics of Operation Research"},{"issue":"4","key":"23_CR18","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/0607063","volume":"7","author":"G. Mitchison","year":"1986","unstructured":"G. Mitchison and R. Durbin. Optimal numberings of an n \u00b5 n array. SIAM J. on Alg. Disc. Math., 7(4):571\u2013582, 1986.","journal-title":"SIAM J. on Alg. Disc. Math."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0025-5564(70)90061-1","volume":"6","author":"R. Miles","year":"1970","unstructured":"R. Miles. On the homogeneous planar poisson point process. Mat. Bioscience, 6:85\u2013125, 1970.","journal-title":"Mat. Bioscience"},{"issue":"70","key":"23_CR20","first-page":"21","volume":"1","author":"D.O. Muradyan","year":"1980","unstructured":"D.O. Muradyan and T.E. Piliposjan. Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR, 1(70):21\u201327, 1980. In Russian.","journal-title":"Akad. Nauk. Armjan. SRR"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"23_CR22","unstructured":"C.H. Papadimitriou. The probabilistic analysis of matching heuristics. In Proc. 15th. Annual Conference on Comm. Control Computing., pages 368\u2013378, 1978."},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1214\/aoap\/1034625335","volume":"7","author":"M. Penrose","year":"1997","unstructured":"M. Penrose. The longest edge of the random minimal spanning tree. The Annals of Applied Probability., 7:340\u2013361, 1997.","journal-title":"The Annals of Applied Probability"},{"key":"23_CR24","unstructured":"M. Penrose. On the k-connectivity for a geometric random graph. Technical report, Department of Mathematical Science. University of Durham., 1997."},{"key":"23_CR25","unstructured":"J. Petit i Silvestre. Approximation Heuristics and Benchmarkings for the MinLA Problem. In R. Battiti and A. Bertossi, editors, Alex\u2019 98 \u2014 Building bridges between theory and applications, 1998."},{"key":"23_CR26","unstructured":"S. Rao and A. W. Richa. New Approximation Techniques for Some Ordering Problems. In 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 211\u2013218, 1998."},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"M.I. Shamos and D. Hoey. Closest-point problems. In Proc. 16th IEEE Annual Symposium on Foundations of Computer Science, pages 224\u2013233, 1975.","DOI":"10.1109\/SFCS.1975.8"},{"key":"23_CR28","doi-asserted-by":"publisher","first-page":"524","DOI":"10.2307\/3214195","volume":"23","author":"J.M. Steele","year":"1986","unstructured":"J.M. Steele and L. Tierney. Boundary domination and the distribution of the largest nearest-neighbpr link in higher dimensions. Journal Applied Probability., 23:524\u2013528, 1986.","journal-title":"Journal Applied Probability"},{"key":"23_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J.M. Steele","year":"1981","unstructured":"J.M. Steele. Subadditive euclidean functional and nonlinear growth in geometric probability. Annals of Probability., 9:365\u2013376, 1981.","journal-title":"Annals of Probability"},{"key":"23_CR30","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1287\/moor.11.2.343","volume":"11","author":"J.M. Steele","year":"1986","unstructured":"J.M. Steele. Probabilistic algorithm for the directed traveling salesman problem. Math. od Operation Research., 11:343\u2013350, 1986.","journal-title":"Math. od Operation Research"},{"key":"23_CR31","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1214\/aop\/1176991596","volume":"16","author":"J.M. Steele","year":"1988","unstructured":"J.M. Steele. Growth rates of euclidean minimal spanning trees with power weighted edges. Annals of Probability., 16:1767\u20131787, 1988.","journal-title":"Annals of Probability"},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"J.M. Steele. Probability theory and Combinatorial Optimization. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics., 1997.","DOI":"10.1137\/1.9781611970029"},{"key":"23_CR33","unstructured":"B. Weide. Statistical Methods in Algorithmic Design and Analysis. Phd thesis, Department of Computer Science, Carnegie-Mellon University, 1978."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T01:08:44Z","timestamp":1550365724000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}