{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:54:25Z","timestamp":1780073665609,"version":"3.54.0"},"reference-count":25,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1994,8,1]],"date-time":"1994-08-01T00:00:00Z","timestamp":775699200000},"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":6925,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1994,8]]},"DOI":"10.1016\/0304-3975(94)90155-4","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T00:17:21Z","timestamp":1027642641000},"page":"125-138","source":"Crossref","is-referenced-by-count":46,"title":["Constructing competitive tours from local information"],"prefix":"10.1016","volume":"130","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kirk R.","family":"Pruhs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)90155-4_BIB1","first-page":"337","article-title":"On-line Steiner trees in the Euclidean plane","author":"Alon","year":"1992","journal-title":"Proc. 8th ACM Symp. on Computational Geometry"},{"key":"10.1016\/0304-3975(94)90155-4_BIB2","unstructured":"Y. Azar, Lower bounds for insertion methods for TSP, manuscript."},{"key":"10.1016\/0304-3975(94)90155-4_BIB3","unstructured":"R. Baeza-Yates, J. Culberson and G. Rawlins, Searching with uncertainty, Inform. and Comput., to appear."},{"key":"10.1016\/0304-3975(94)90155-4_BIB4","doi-asserted-by":"crossref","unstructured":"V. Bafna, B. Kalyanasundaram and K. Pruhs, Not all insertion methods yield constant approximate tours in the plane, Theoret. Comput. Sci., to appear.","DOI":"10.1016\/0304-3975(94)90257-7"},{"key":"10.1016\/0304-3975(94)90155-4_BIB5","first-page":"237","article-title":"On-line navigation in a room","author":"Bar-Eli","year":"1991","journal-title":"Proc. 2nd Ann. SIAM\/ACM Conf. on Discrete Algorithms"},{"key":"10.1016\/0304-3975(94)90155-4_BIB6","first-page":"261","article-title":"The Canadian travelers problem","author":"Bar-Noy","year":"1991","journal-title":"Proc. 2nd Ann. ACM\/SIAM Symp. on Discrete Algorithms"},{"key":"10.1016\/0304-3975(94)90155-4_BIB7","first-page":"494","article-title":"Navigating in unfamiliar geometric terrain","author":"Blum","year":"1991","journal-title":"Proc. 23rd Ann. ACM Symp. of Theory of Computing"},{"key":"10.1016\/0304-3975(94)90155-4_BIB8","unstructured":"B. Chandra and S. Vishwanathan, Constructing reliable communication networks of small weight online, manuscript."},{"key":"10.1016\/0304-3975(94)90155-4_BIB9","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/0304-3975(94)90155-4_BIB10","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","article-title":"Which triangulations approximate the complete graph","author":"Das","year":"1989","journal-title":"Proc. Internat. Symp. on Optimal Algorithms"},{"key":"10.1016\/0304-3975(94)90155-4_BIB11","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1109\/SFCS.1991.185382","article-title":"How to learn an unknown environment","author":"Deng","year":"1991","journal-title":"Proc. 32nd Ann. Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(94)90155-4_BIB12","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1109\/FSCS.1990.89554","article-title":"Exploring an unknown graph","author":"Deng","year":"1990","journal-title":"Proc. 31st Ann. Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(94)90155-4_BIB13","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1109\/SFCS.1991.185381","article-title":"Competitive algorithms for layered graph traversal","author":"Fiat","year":"1991","journal-title":"Proc. 32nd Ann. Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(94)90155-4_BIB14","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","article-title":"Dynamic Steiner tree problem","volume":"4","author":"Imase","year":"1991","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0304-3975(94)90155-4_BIB15","series-title":"Tech. Report","article-title":"Constructing competitive tours from local information","author":"Kalyanasundaram","year":"1992"},{"key":"10.1016\/0304-3975(94)90155-4_BIB16","first-page":"147","article-title":"A competitive analysis of nearest neighbor algorithms for searching unknown scenes","author":"Kalyanasundaram","year":"1992","journal-title":"Proc. 9th Ann. Symp. on Theoretical Aspects of Computer Science"},{"key":"10.1016\/0304-3975(94)90155-4_BIB17","first-page":"278","article-title":"Lower bounds for randomized k-server and motion planning algorithms","author":"Karloff","year":"1991","journal-title":"Proc. 23rd Ann. ACM Symp. of Theory of Computing"},{"key":"10.1016\/0304-3975(94)90155-4_BIB18","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1109\/SFCS.1991.185383","article-title":"Walking an unknown street with bounded detour","author":"Klein","year":"1991","journal-title":"Proc. 32nd Ann. Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(94)90155-4_BIB19","series-title":"The Traveling Salesman Problem","author":"Lawier","year":"1985"},{"key":"10.1016\/0304-3975(94)90155-4_BIB20","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/3-540-51859-2_2","article-title":"There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees","author":"Levcopoulos","year":"1989","journal-title":"Proc. Internat. Symp. on Optimal Algorithms"},{"key":"10.1016\/0304-3975(94)90155-4_BIB21","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/BFb0035787","article-title":"Shortest paths without a map","author":"Papadimitriou","year":"1989","journal-title":"Proc. 16th Ann. Internat. Coll. on Automata, Languages, and Programming"},{"key":"10.1016\/0304-3975(94)90155-4_BIB22","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1145\/76359.76361","article-title":"Spacefilling curves and the planar traveling salesman problem","volume":"36","author":"Platzman","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)90155-4_BIB23","series-title":"Computational Geometry: An Introduction","author":"Preparata","year":"1985"},{"key":"10.1016\/0304-3975(94)90155-4_BIB24","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An analysis of several heuristics for the traveling salesman problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)90155-4_BIB25","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","article-title":"The relative neighborhood graph of a finite planar set","volume":"12","author":"Toussaint","year":"1980","journal-title":"Pattern Recognition"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397594901554?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397594901554?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T09:17:44Z","timestamp":1580894264000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397594901554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,8]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,8]]}},"alternative-id":["0304397594901554"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)90155-4","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1994,8]]}}}