{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:32:10Z","timestamp":1759847530716},"reference-count":38,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1990,10,1]],"date-time":"1990-10-01T00:00:00Z","timestamp":654739200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8325,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Theory, Series B"],"published-print":{"date-parts":[[1990,10]]},"DOI":"10.1016\/0095-8956(90)90097-j","type":"journal-article","created":{"date-parts":[[2005,2,9]],"date-time":"2005-02-09T09:37:08Z","timestamp":1107941828000},"page":"65-81","source":"Crossref","is-referenced-by-count":8,"title":["Quantizers and the worst-case Euclidean traveling salesman problem"],"prefix":"10.1016","volume":"50","author":[{"given":"Luis A.","family":"Goddyn","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0095-8956(90)90097-J_BIB1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0604005","article-title":"The optimal lattice quantizer in three dimensions","volume":"4","author":"Barnes","year":"1983","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0095-8956(90)90097-J_BIB2","first-page":"299","article-title":"The shortest path through many points","volume":"55","author":"Beardwood","year":"1959"},{"key":"10.1016\/0095-8956(90)90097-J_BIB3","author":"Christofides","year":"1981"},{"key":"10.1016\/0095-8956(90)90097-J_BIB4","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF00149359","article-title":"On Steiner trees for bounded point sets","volume":"11","author":"Chung","year":"1981","journal-title":"Geom. Dedicata"},{"key":"10.1016\/0095-8956(90)90097-J_BIB5","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/TIT.1985.1056993","article-title":"A lower bound on the average error of vector quantizers","volume":"IT-31","author":"Conway","year":"1985","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0095-8956(90)90097-J_BIB6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1109\/TIT.1982.1056483","article-title":"Voronoi regions of lattices, second moments of polytopes, and quantization","volume":"IT-28","author":"Conway","year":"1982","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0095-8956(90)90097-J_BIB7","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1109\/TIT.1982.1056484","article-title":"Fast quantizing and decoding algorithms for lattice quantizers and codes","volume":"IT-28","author":"Conway","year":"1982","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0095-8956(90)90097-J_BIB8","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0605031","article-title":"On the Voronoi regions of certain lattices","volume":"5","author":"Conway","year":"1984","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0095-8956(90)90097-J_BIB9","author":"Conway","year":"1988"},{"key":"10.1016\/0095-8956(90)90097-J_BIB10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0020-0190(84)90024-3","article-title":"A partitioning algorithm for minimum weighted Euclidean matching","volume":"18","author":"Dyer","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0095-8956(90)90097-J_BIB11","first-page":"83","article-title":"Uber mein geometrischen Satz","volume":"46","author":"Fejes-Toth","year":"1940"},{"key":"10.1016\/0095-8956(90)90097-J_BIB12","series-title":"Convexity and Its Applications","first-page":"318","article-title":"New results in the theory of packing and covering","author":"Fejes-Toth","year":"1983"},{"key":"10.1016\/0095-8956(90)90097-J_BIB13","author":"Fejes-Toth","year":"1964"},{"key":"10.1016\/0095-8956(90)90097-J_BIB14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1112\/S0025579300000784","article-title":"The shortest path and the shortest road through n points","volume":"2","author":"Few","year":"1955","journal-title":"Mathematika"},{"key":"10.1016\/0095-8956(90)90097-J_BIB15","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1109\/TIT.1979.1056067","article-title":"Asymptotically optimal block quantization","volume":"IT-25","author":"Gersho","year":"1979","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0095-8956(90)90097-J_BIB16","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1177\/0008068319490207","article-title":"Expected travel among random points","volume":"2","author":"Ghosh","year":"1948","journal-title":"Bull. Calcutta Statist. Ass."},{"key":"10.1016\/0095-8956(90)90097-J_BIB17","unstructured":"A. G. Goldstein and E. M. Reingold, \u201cImproved Bounds on the Traveling Salesman Problem in the Unit Cube\u201d, Manuscript, Department of Computer Science, University of Illinois at Urbana-Champaign, Illinois."},{"key":"10.1016\/0095-8956(90)90097-J_BIB18","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1137\/0401006","article-title":"Extremum properties of hexagonal partitioning and the uniform distribution in Euclidean Location","volume":"1","author":"Haimovich","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0095-8956(90)90097-J_BIB19","unstructured":"J. H. Halton and R. Terada, An Almost Surely Optimal Algorithm for the Euclidean Traveling Salesman Problem\u201d, Technical Report No. 335, Computer Sciences Dept., University of Wisconsin."},{"key":"10.1016\/0095-8956(90)90097-J_BIB20","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0211003","article-title":"A fast algorithm for the Euclidean traveling salesman problem, optimal with probability one","volume":"11","author":"Halton","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0095-8956(90)90097-J_BIB21","first-page":"3","article-title":"Bounds for packings on the sphere and in space","volume":"14","author":"Kabatjanskii","year":"1978","journal-title":"Problemy Peredachi Informatsii"},{"key":"10.1016\/0095-8956(90)90097-J_BIB22","author":"Karloff","year":"1987"},{"key":"10.1016\/0095-8956(90)90097-J_BIB23","series-title":"Algorithms and Complexity: New Directions and Recent Results","first-page":"209","article-title":"Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane","author":"Karp","year":"1977"},{"key":"10.1016\/0095-8956(90)90097-J_BIB24","series-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","article-title":"Probabilistic analysis of heuristics","author":"Karp","year":"1985"},{"key":"10.1016\/0095-8956(90)90097-J_BIB25","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0095-8956(84)90067-4","article-title":"On the length of optimal TSP circuits in sets of bounded diameter","volume":"37","author":"Moran","year":"1984","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/0095-8956(90)90097-J_BIB26","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1109\/TIT.1982.1056492","article-title":"The hexagonal theorem","volume":"IT-28","author":"Newman","year":"1982","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0095-8956(90)90097-J_BIB27","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"The Euclidean salesman traveling problem is NP-complete","volume":"4","author":"Papadimitriou","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0095-8956(90)90097-J_BIB28","series-title":"Proceedings of the 15th Allerton Conference in Commmunication, Control and Computiner","first-page":"361","article-title":"The probabilistic analyses of matching heuristics","author":"Papadimitrioui","year":"1977"},{"key":"10.1016\/0095-8956(90)90097-J_BIB29","author":"Rogers","year":"1964"},{"key":"10.1016\/0095-8956(90)90097-J_BIB30","unstructured":"J. M. Steele, \u201cProbabilistic and Worst Case Analyses of Some Problems of Combinatorial Optimization in Euclidean Space\u201d, Technical Report, Program in Operations Research and Statistics, Princeton University, Princeton, NJ."},{"key":"10.1016\/0095-8956(90)90097-J_BIB31","doi-asserted-by":"crossref","unstructured":"J. M. Steele, T. L. Snyder, Worst case growth rates of some classical problems of combinatorial optimization, SIAM J. Comput., to appear.","DOI":"10.1137\/0218019"},{"key":"10.1016\/0095-8956(90)90097-J_BIB32","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0212009","article-title":"The traveling salesman problem and minimum matching in the unit square","volume":"12","author":"Supowit","year":"1983","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0095-8956(90)90097-J_BIB33","first-page":"352","article-title":"On nogle geometriks taltheoretiske theoremer","volume":"14","author":"Thue","year":"1982","journal-title":"Fordht. Skand. Naturforsk"},{"key":"10.1016\/0095-8956(90)90097-J_BIB34","first-page":"904","article-title":"On the shortest path through a number of points","volume":"2","author":"Verblunsky","year":"1951"},{"key":"10.1016\/0095-8956(90)90097-J_BIB35","first-page":"A85","article-title":"Euclidean matching problems and the metropolis algorithm","volume":"30","author":"Weber","year":"1986","journal-title":"Z. Oper. Res."},{"key":"10.1016\/0095-8956(90)90097-J_BIB36","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1017\/S1446788700029402","article-title":"The Voronoi region of E6\u2217","volume":"48","author":"Worley","year":"1987","journal-title":"J. Austral. Math. Soc. Ser. A"},{"key":"10.1016\/0095-8956(90)90097-J_BIB37","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/0401015","article-title":"The Voronoi region of E7\u2217","volume":"1","author":"Worley","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0095-8956(90)90097-J_BIB38","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/TIT.1982.1056490","article-title":"Asymptotic quantization error of continuous signals and the quantization dimension","volume":"IT-28","author":"Zador","year":"1982","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Journal of Combinatorial Theory, Series B"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:009589569090097J?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:009589569090097J?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T10:52:14Z","timestamp":1548759134000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/009589569090097J"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,10]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,10]]}},"alternative-id":["009589569090097J"],"URL":"https:\/\/doi.org\/10.1016\/0095-8956(90)90097-j","relation":{},"ISSN":["0095-8956"],"issn-type":[{"value":"0095-8956","type":"print"}],"subject":[],"published":{"date-parts":[[1990,10]]}}}