{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T13:57:42Z","timestamp":1770559062879,"version":"3.49.0"},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1990,1]]},"DOI":"10.1007\/bf01585751","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:12:20Z","timestamp":1114679540000},"page":"361-378","source":"Crossref","is-referenced-by-count":13,"title":["On patching algorithms for random asymmetric travelling salesman problems"],"prefix":"10.1007","volume":"46","author":[{"given":"M. E.","family":"Dyer","sequence":"first","affiliation":[]},{"given":"A. M.","family":"Frieze","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. Angluin and L.G. Valient, \u201cFast probabilistic algorithms for hamilton circuits and matchings,\u201dJournal of Computer and System Sciences 18 (1979) 155\u2013193.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR2","first-page":"361","volume-title":"The Travelling Salesman Problem","author":"E. Balas","year":"1984","unstructured":"E. Balas and P. Toth, \u201cBranch and bound methods,\u201d in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Travelling Salesman Problem (Wiley, Chichester, UK, 1984) pp. 361\u2013401."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"G.N. Frederickson","year":"1978","unstructured":"G.N. Frederickson, M.S. Hecht and C.E. Kim, \u201cApproximation algorithms for some routing problems,\u201dSIAM Journal on Computing 7 (1978) 178\u2013193.","journal-title":"SIAM Journal on Computing"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A.M. Frieze","year":"1985","unstructured":"A.M. Frieze and G.R. Grimmett, \u201cThe shortest path problem for graphs with random arc-lengths,\u201dDiscrete Applied Mathematics 10 (1985) 57\u201377.","journal-title":"Discrete Applied Mathematics"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding, \u201cProbability inequalities for sums of bounded random variables,\u201dJournal of the American Statistical Association 58 (1963) 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/0208045","volume":"8","author":"R.M. Karp","year":"1979","unstructured":"R.M. Karp, \u201cA patching algorithm for the non-symmetric travelling salesman problem,\u201dSIAM Journal on Computing 8 (1979) 561\u2013573.","journal-title":"SIAM Journal on Computing"},{"key":"CR7","first-page":"181","volume-title":"The Travelling Salesman Problem","author":"R.M. Karp","year":"1984","unstructured":"R.M. Karp and J.M. Steele, \u201cProbabilistic analysis of heuristics,\u201d in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Travelling Salesman Problem (Wiley, Chichester, UK, 1984) pp. 181\u2013205."},{"key":"CR8","volume-title":"Combinatorial Optimisation: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler,Combinatorial Optimisation: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976)."},{"key":"CR9","volume-title":"The Travelling Sales Problem","year":"1984","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Travelling Sales Problem (Wiley, Chichester, UK, 1984)."},{"key":"CR10","volume-title":"Combinatorial Optimisation: Algorithms and Complexity","author":"C.H. Papidimitrious","year":"1982","unstructured":"C.H. Papidimitrious and K. Steiglitz,Combinatorial Optimisation: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585751.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585751\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585751","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:32:31Z","timestamp":1556897551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,1]]},"references-count":10,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1990,1]]}},"alternative-id":["BF01585751"],"URL":"https:\/\/doi.org\/10.1007\/bf01585751","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,1]]}}}