{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:49:02Z","timestamp":1776106142742,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897571","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"22-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Separating subadditive euclidean functionals"],"prefix":"10.1145","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wesley","family":"Pegden","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1374811"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"F. Avram and D. Bertsimas The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach in The Annals of Applied Probability 2 (1992) 113\u2013130.  F. Avram and D. Bertsimas The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach in The Annals of Applied Probability 2 (1992) 113\u2013130.","DOI":"10.1214\/aoap\/1177005773"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762114"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90066-E"},{"key":"e_1_3_2_1_6_1","volume-title":"Combinatorial Optimization","author":"Christofides N.","year":"1971","unstructured":"N. Christofides , The Traveling Salesman Problem , in Combinatorial Optimization , N. Christofides, P. Toth, A. Mingozzi and C. Sandi, Eds., John Wiley and Sons , New York , 1971 . N. Christofides, The Traveling Salesman Problem, in Combinatorial Optimization, N. Christofides, P. Toth, A. Mingozzi and C. Sandi, Eds., John Wiley and Sons, New York, 1971."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"F.R.K. Chung and R.L. Graham On Steiner trees for bounded point sets in Geometriae Dedicata 11 (1981) 353\u2013361.  F.R.K. Chung and R.L. Graham On Steiner trees for bounded point sets in Geometriae Dedicata 11 (1981) 353\u2013361.","DOI":"10.1007\/BF00149359"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2004.831130"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"G.B. Dantzig D.R. Fulkerson and S.M. Johnson Solution of a large scale traveling salesman problenm Operations Research 2 (1954) 393-410.  G.B. Dantzig D.R. Fulkerson and S.M. Johnson Solution of a large scale traveling salesman problenm Operations Research 2 (1954) 393-410.","DOI":"10.1287\/opre.2.4.393"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0105"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0113021"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"M.X. Goemans and D.J. Bertsimas Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem Mathematics of Operations Research 16 (1991) 72-89.  M.X. Goemans and D.J. Bertsimas Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem Mathematics of Operations Research 16 (1991) 72-89.","DOI":"10.1287\/moor.16.1.72"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and L. Schrijver The ellipsoid method and its consequences in combinatorial optimization Combinatorica 1 (1981) 169-197.  M. Gr\u00f6tschel L. Lov\u00e1sz and L. Schrijver The ellipsoid method and its consequences in combinatorial optimization Combinatorica 1 (1981) 169-197.","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_15_1","first-page":"87","volume":"7","author":"Helbig Hansen K.","year":"1974","unstructured":"K. Helbig Hansen and J. Krarup , Improvements of the Held-Karp Algorithm for the symmetric Traveling Salesman Problem, Mathematical Programming 7 ( 1974 ) 87 - 96 . K. Helbig Hansen and J. Krarup, Improvements of the Held-Karp Algorithm for the symmetric Traveling Salesman Problem, Mathematical Programming 7 (1974) 87-96.","journal-title":"Improvements of the Held-Karp Algorithm for the symmetric Traveling Salesman Problem, Mathematical Programming"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"F. K. Hwang and Y. C. Yao Comments on Bern\u2019s probabilistic results on rectilinear Steiner trees in Algorithmica 5 (1990) 591\u2013598.  F. K. Hwang and Y. C. Yao Comments on Bern\u2019s probabilistic results on rectilinear Steiner trees in Algorithmica 5 (1990) 591\u2013598.","DOI":"10.1007\/BF01840406"},{"key":"e_1_3_2_1_19_1","volume-title":"Talk presented at the Mathematical Programming Symposium","author":"Johnson D.","year":"1988","unstructured":"D. Johnson , Talk presented at the Mathematical Programming Symposium , Tokyo , 1988 . D. Johnson, Talk presented at the Mathematical Programming Symposium, Tokyo, 1988."},{"key":"e_1_3_2_1_20_1","first-page":"341","volume-title":"Proceedings of the 7th Annual ACM Symposium on Discrete Algorithms (1991)","author":"Johnson D.","unstructured":"D. Johnson , L. Mcgeoch and E. Rothberg , Asymptotic Experimental Analysis of the Held-Karp Traveling Salesman Bound , Proceedings of the 7th Annual ACM Symposium on Discrete Algorithms (1991) 341 - 350 . D. Johnson, L. Mcgeoch and E. Rothberg, Asymptotic Experimental Analysis of the Held-Karp Traveling Salesman Bound, Proceedings of the 7th Annual ACM Symposium on Discrete Algorithms (1991) 341-350."},{"key":"e_1_3_2_1_21_1","first-page":"188","volume":"141","author":"McDiarmid C.","year":"1989","unstructured":"C. McDiarmid , On the Method of Bounded Differences , Surveys in Combinatorics 141 ( 1989 ) 148\u02c6 a \u02d8 A\u00b8 S 188 . C. McDiarmid, On the Method of Bounded Differences, Surveys in Combinatorics 141 (1989) 148\u02c6 a \u02d8 A\u00b8 S188.","journal-title":"Surveys in Combinatorics"},{"key":"e_1_3_2_1_22_1","first-page":"754","volume":"251","author":"Miller D.","unstructured":"D. Miller and J. Pekny , Exact Solution of Large Asymmetric Traveling Salesman Problems, in Science 251 754 \u2013 761 . D. Miller and J. Pekny, Exact Solution of Large Asymmetric Traveling Salesman Problems, in Science 251 754\u2013761.","journal-title":"Exact Solution of Large Asymmetric Traveling Salesman Problems, in Science"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"e_1_3_2_1_24_1","volume-title":"Proc. 15th Conference Comm. Contr. Computing","author":"Papadimitriou C. H.","unstructured":"C. H. Papadimitriou , The probabilistic analysis of matching heuristics , in Proc. 15th Conference Comm. Contr. Computing . Univ. Illinois. C. H. Papadimitriou, The probabilistic analysis of matching heuristics, in Proc. 15th Conference Comm. Contr. Computing. Univ. Illinois."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030302"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"T. Smith and G. Thompson A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman problem Using Held and Karp\u2019s 1-Tree Relaxation Annals of Discrete Mathematics 1 (1977) 479-493.  T. Smith and G. Thompson A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman problem Using Held and Karp\u2019s 1-Tree Relaxation Annals of Discrete Mathematics 1 (1977) 479-493.","DOI":"10.1016\/S0167-5060(08)70754-4"},{"key":"e_1_3_2_1_27_1","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science 497\u2013507","author":"Srivastav A.","unstructured":"A. Srivastav and S. Werth , Probabilistic analysis of the degree bounded minimum spanning tree problem , in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science 497\u2013507 . A. Srivastav and S. Werth, Probabilistic analysis of the degree bounded minimum spanning tree problem, in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science 497\u2013507."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994411"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218019"},{"key":"e_1_3_2_1_30_1","series-title":"SIAM CBMS series","volume-title":"Probability Theory and Combinatorial Optimization","author":"Steele J. Michael","year":"1996","unstructured":"J. Michael Steele , Probability Theory and Combinatorial Optimization , SIAM CBMS series , 1996 . J. Michael Steele, Probability Theory and Combinatorial Optimization, SIAM CBMS series, 1996."},{"key":"e_1_3_2_1_31_1","first-page":"809","volume":"24","author":"Steele J. M.","year":"1987","unstructured":"J. M. Steele , L. A. Shepp and W. F. Eddy , On the Number of Leaves of a Euclidean Minimal Spanning Tree, Journal of Applied Probability 24 ( 1987 ) 809 \u2013 826 . J. M. Steele, L. A. Shepp and W. F. Eddy, On the Number of Leaves of a Euclidean Minimal Spanning Tree, Journal of Applied Probability 24 (1987) 809\u2013826.","journal-title":"On the Number of Leaves of a Euclidean Minimal Spanning Tree, Journal of Applied Probability"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"S. Steinerberger New Bounds for the Traveling Salesman Constant Advances in Applied Probability 47 (2013)  S. Steinerberger New Bounds for the Traveling Salesman Constant Advances in Applied Probability 47 (2013)","DOI":"10.1239\/aap\/1427814579"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"L. T\u00f3th \u00dcber einen geometrischen Satz Mathematische Zeitschrift 46 (in German) (1940) 83-85.  L. T\u00f3th \u00dcber einen geometrischen Satz Mathematische Zeitschrift 46 (in German) (1940) 83-85.","DOI":"10.1007\/BF01181430"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"T. Volgenant and R. Jonker A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem based on the 1-tree Relaxation European Journal of Operations Research 9 (1982) 83-89.  T. Volgenant and R. Jonker A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem based on the 1-tree Relaxation European Journal of Operations Research 9 (1982) 83-89.","DOI":"10.1016\/0377-2217(82)90015-7"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897571","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:57Z","timestamp":1750222557000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":34,"alternative-id":["10.1145\/2897518.2897571","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897571","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}