{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T18:21:59Z","timestamp":1773080519155,"version":"3.50.1"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>We consider a variation of the Travelling Salesman Problem (TSP) in which the cities visited have non-zero spatial extent, in contrast with the classical TSP, which has destinations that are mathematical points. This new approach opens up both new analyses of the problem and new algorithms for solutions, while remaining an economic first approximation to the standard problem. We present one particular solution that, depending on the number and size of the cities, can improve existing algorithms solving the classical TSP.<\/jats:p>","DOI":"10.1017\/s096012951000037x","type":"journal-article","created":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T06:00:45Z","timestamp":1289196045000},"page":"1067-1078","source":"Crossref","is-referenced-by-count":1,"title":["The Travelling Salesman Problem for finite-sized cities"],"prefix":"10.1017","volume":"20","author":[{"given":"HUGO","family":"FORT","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MORDECHAI","family":"KORNBLUTH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FREDY","family":"ZYPMAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"key":"S096012951000037X_ref8","volume-title":"Computational Complexity and Statistical Physics","author":"Percus","year":"2006"},{"key":"S096012951000037X_ref4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"S096012951000037X_ref2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.2.125"},{"key":"S096012951000037X_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"S096012951000037X_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00030-6"},{"key":"S096012951000037X_ref6","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600680"},{"key":"S096012951000037X_ref7","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"S096012951000037X_ref1","first-page":"331","article-title":"Where the Really Hard Problems Are","volume":"1","author":"Cheeseman","year":"1991","journal-title":"Proceedings of 12th International Joint Conference on AI (IJCAI-91)"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096012951000037X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T16:32:36Z","timestamp":1556382756000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096012951000037X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"references-count":8,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["S096012951000037X"],"URL":"https:\/\/doi.org\/10.1017\/s096012951000037x","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,8]]}}}