{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:09:50Z","timestamp":1759666190007},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,3,7]],"date-time":"2012-03-07T00:00:00Z","timestamp":1331078400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s10589-012-9472-0","type":"journal-article","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T11:02:18Z","timestamp":1331031738000},"page":"711-728","source":"Crossref","is-referenced-by-count":2,"title":["Computing the variance of tour costs over the solution space of the TSP in polynomial time"],"prefix":"10.1007","volume":"53","author":[{"given":"Paul J.","family":"Sutcliffe","sequence":"first","affiliation":[]},{"given":"Andrew","family":"Solomon","sequence":"additional","affiliation":[]},{"given":"Jenny","family":"Edwards","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,3,7]]},"reference":[{"issue":"8","key":"9472_CR1","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1101\/gr.10.3.350","volume":"10","author":"R. Agarwala","year":"2000","unstructured":"Agarwala, R., Applegate, D., Maglott, D., Schuler, G., Schaffer, A.: A fast and scalable radiation hybrid map construction and integration strategy. Genome Res. 10(8), 350\u2013364 (2000)","journal-title":"Genome Res."},{"key":"9472_CR2","series-title":"Princeton Series in Applied Mathematics","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"D.L. Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2006)"},{"issue":"5","key":"9472_CR3","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"9472_CR4","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0893-9659(03)80054-X","volume":"16","author":"J. Barnes","year":"2003","unstructured":"Barnes, J., Dimova, B., Dokov, S., Solomon, A.: The theory of elementary landscapes. Appl. Math. Lett. 16(3), 337\u2013343 (2003)","journal-title":"Appl. Math. Lett."},{"issue":"2","key":"9472_CR5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1011263204536","volume":"20","author":"J. Basel III","year":"2001","unstructured":"Basel, J. III, Willemain, T.R.: Random tours in the traveling salesman problem analysis and application. Comput. Optim. Appl. 20(2), 211\u2013217 (2001)","journal-title":"Comput. Optim. Appl."},{"key":"9472_CR6","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"Beardwood, J., Halton, J., Hammersley, J.: The shortest path through many points. Proc. Camb. Philos. Soc. 55, 299\u2013327 (1959)","journal-title":"Proc. Camb. Philos. Soc."},{"issue":"1","key":"9472_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0893-9659(00)00120-8","volume":"14","author":"B. Colletti","year":"2001","unstructured":"Colletti, B., Barnes, J.: Local search structure in the symmetric travelling salesperson problem under a general class of rearrangement neighborhoods. Appl. Math. Lett. 14(1), 105\u2013108 (2001)","journal-title":"Appl. Math. Lett."},{"key":"9472_CR8","first-page":"7","volume-title":"Proc. of ECCB-06","author":"T. Faraut","year":"2007","unstructured":"Faraut, T., de Givry, S., Chabrier, P., Derrien, T., Galibert, F., Hitte, C., Schiex, T.: A comparative genome approach to marker ordering. In: Proc. of ECCB-06, p.\u00a07 (2007)"},{"issue":"4","key":"9472_CR9","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1287\/moor.1040.0105","volume":"29","author":"A. Frieze","year":"2004","unstructured":"Frieze, A.: On random symmetric travelling salesman problems. Math. Oper. Res. 29(4), 878\u2013890 (2004)","journal-title":"Math. Oper. Res."},{"key":"9472_CR10","first-page":"256","volume-title":"The Traveling Salesman Problem and its Variations","author":"A. Frieze","year":"2002","unstructured":"Frieze, A., Yukich, J.E.: Probabilistic analysis of the TSP. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and its Variations, pp. 256\u2013307. Kluwer Academic, New York (2002)"},{"key":"9472_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)"},{"key":"9472_CR12","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Punnen, A.: The Traveling Salesman Problem and Its Variations. Kluwer Academic, New York (2002)"},{"issue":"1\u20132","key":"9472_CR13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Appl. Math. 119(1\u20132), 107\u2013116 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9472_CR14","series-title":"Algorithms and Combinatorics","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","year":"1998","unstructured":"Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.): Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics, vol.\u00a016. Springer, Berlin (1998)"},{"issue":"8","key":"9472_CR15","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1038\/nrg1658","volume":"6","author":"C. Hitte","year":"2005","unstructured":"Hitte, C., Madeoy, J., Kirkness, E., Priat, C., Lorentzen, T., Senger, F., Thomas, D., Derrien, T., Ramirez, C., Scott, C., Evanno, G., Pullar, B., Cadieu, E., Oza, V., Lourgant, K., Jaffe, D., Tacher, S., Dr\u00e9ano, S., Berkova, N., Andr\u00e9, C., Deloukas, P., Fraser, C., Lindblad-Toh, K., Ostrander, E., Galibert,\u00a0F.: Facilitating genome navigation, survey sequencing and dense radiation-hybrid gene mapping. Nat. Rev. Genet. 6(8), 643\u2013648 (2005)","journal-title":"Nat. Rev. Genet."},{"issue":"3","key":"9472_CR16","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R. Karp","year":"1977","unstructured":"Karp, R.: 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."},{"issue":"4598","key":"9472_CR17","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D. Jr., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"issue":"3","key":"9472_CR18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1209\/0295-5075\/8\/3\/002","volume":"8","author":"W. Krauth","year":"1988","unstructured":"Krauth, W., M\u00e9zard, M.: The cavity method and the travelling-salesman problem. Europhys. Lett. 8(3), 213\u2013218 (1988)","journal-title":"Europhys. Lett."},{"key":"9472_CR19","volume-title":"The Traveling Salesman Problem","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B. (eds.): The Traveling Salesman Problem. Wiley, New York (1985)"},{"key":"9472_CR20","volume-title":"Optimization by Vector Space Methods","author":"D.G. Luenberger","year":"1997","unstructured":"Luenberger, D.G.: Optimization by Vector Space Methods. Wiley, New York (1997)"},{"issue":"8","key":"9472_CR21","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1051\/jphys:019860047080128500","volume":"47","author":"M. M\u00e9zard","year":"1986","unstructured":"M\u00e9zard, M., Parisi, G.: A replica analysis of the travelling salesman problem. J. Phys. (Paris) 47(8), 1285\u20131296 (1986)","journal-title":"J. Phys. (Paris)"},{"key":"9472_CR22","first-page":"91","volume-title":"Optimisation, Econometric and Financial Analysis (Advances in Computational Management Science)","author":"A.J. Orman","year":"2006","unstructured":"Orman, A.J., Williams, H.P.: A survey of different integer programming formulations of the travelling salesman problem. In: Kontoghiorghes, E.J., Gatu, C. (eds.) Optimisation, Econometric and Financial Analysis (Advances in Computational Management Science), pp. 91\u2013104. Springer, Berlin (2006)"},{"key":"9472_CR23","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach","author":"P.A. Pevzner","year":"2000","unstructured":"Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000)"},{"issue":"4","key":"9472_CR24","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB\u2014a traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"key":"9472_CR25","series-title":"LNCS","volume-title":"The Traveling Salesman: Computational Solutions for TSP Applications","author":"G. Reinelt","year":"1994","unstructured":"Reinelt, G.: The Traveling Salesman: Computational Solutions for TSP Applications. LNCS, vol.\u00a0840. Springer, Berlin (1994)."},{"key":"9472_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aop\/1176991490","volume":"17","author":"W.T. Rhee","year":"1989","unstructured":"Rhee, W.T., Talagrand, M.: A sharp deviation inequality for the stochastic traveling salesman problem. Ann. Probab. 17, 1\u20138 (1989)","journal-title":"Ann. Probab."},{"key":"9472_CR27","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2539-1","volume-title":"Probability","author":"A.N. Shiryaev","year":"1996","unstructured":"Shiryaev, A.N.: Probability, 2nd edn. Graduate Texts in Mathematics. Springer, Berlin (1996)","edition":"2"},{"key":"9472_CR28","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970029","volume-title":"Probability Theory and Combinatorial Optimization","author":"J.M. Steele","year":"1997","unstructured":"Steele, J.M.: Probability Theory and Combinatorial Optimization. SIAM, Philadelphia (1997)"},{"key":"9472_CR29","unstructured":"W\u00e4stlund, J.: The mean field traveling salesman and related problems. Acta Math. (2012, to appear)"},{"key":"9472_CR30","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0093472","volume-title":"Probability Theory of Classical Euclidean Optimization Problems","author":"J.E. Yukich","year":"1998","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol.\u00a01675. Springer, Berlin (1998)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-012-9472-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-012-9472-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-012-9472-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T21:09:37Z","timestamp":1561410577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-012-9472-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,7]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["9472"],"URL":"https:\/\/doi.org\/10.1007\/s10589-012-9472-0","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,7]]}}}