{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:09Z","timestamp":1725664089986},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:38Z","timestamp":1330270658000},"page":"37-48","source":"Crossref","is-referenced-by-count":11,"title":["Serving requests with on-line routing"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Esteban","family":"Feuerstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurizio","family":"Talamo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/0217053","volume":"17","author":"M. Atallah","year":"1988","unstructured":"M. Atallah and S. Kosaraju, Efficient solutions for some transportation problems with application to minimizing robot arm travel, SIAM J. on Computing, 17 (1988), pp. 849\u2013869.","journal-title":"SIAM J. on Computing"},{"key":"4_CR2","unstructured":"S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Widgerson, On the power of randomization in on-line algorithms, Proc. of the 22nd Annual ACM Symposium on Theory of Computing, (1990), pp. 379\u2013386."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"R. El-Yaniv, A. Fiat, R.M. Karp and G. Turpin, Competitive analysis of financial games, Proc. 33rd Annual Symposium on Foundations of Computer Science (1992), pp. 327\u2013333.","DOI":"10.1109\/SFCS.1992.267758"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/0222005","volume":"22-1","author":"G. Frederickson","year":"1993","unstructured":"G. Frederickson, A note on the complexity of a simple transportation problem, SIAM J. on Computing, 22-1 (1993), pp. 57\u201361.","journal-title":"SIAM J. on Computing"},{"key":"4_CR5","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1137\/0221066","volume":"21-6","author":"G. Frederickson","year":"1992","unstructured":"G. Frederickson and D. Guan, Preemptive ensemble motion planning on a tree, SIAM J. on Computing, 21-6 (1992), pp. 1130\u20131152.","journal-title":"SIAM J. on Computing"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/0207017","volume":"7-2","author":"G. Frederickson","year":"1978","unstructured":"G. Frederickson, M. Hecht and C. Kim, Approximation algorithms for some routing problems, SIAM J. on Computing, 7-2 (1978), pp. 178\u2013193.","journal-title":"SIAM J. on Computing"},{"key":"4_CR7","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey, and D. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco (1979)."},{"key":"4_CR8","unstructured":"Y. Karuno, H. Nagamochi and T. Ibaraki: Vehicle scheduling on a tree with release times and handling times, Proc. 4th. International Symposium on Algorithms and Computation ISAAC'93, LNCS 762 (1993), Springer-Verlag, pp. 486\u2013495."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K.R. Pruhs, Constructing competitive tours from local information, Proc. 20th International Colloquium on Automata, Languages and Programming, LNCS 700 (1993), Springer-Verlag.","DOI":"10.1007\/3-540-56939-1_65"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. Manasse","year":"1990","unstructured":"M. Manasse, L.A. McGeoch and D. Sleator, Competitive algorithms for server problems, Journal of Algorithms 11 (1990), pp. 208\u2013230.","journal-title":"Journal of Algorithms"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1287\/mnsc.36.2.212","volume":"36-2","author":"H. Psaraftis","year":"1990","unstructured":"H. Psaraftis, M. Solomon, T. Magnanti and T. Kim, Routing and scheduling on a shoreline with release times, Management Science 36-2 (1990), pp. 212\u2013223.","journal-title":"Management Science"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"D. Sleator, R. Tarjan, Amortized efficiency of list update and paging algorithms, Comm. ACM 28 (1985), pp. 202\u2013208.","journal-title":"Comm. ACM"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. Sleator","year":"1985","unstructured":"D. Sleator, R. Tarjan, Self-adjusting binary search trees, Journal of the ACM, 32 (1985), pp. 652\u2013686.","journal-title":"Journal of the ACM"},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","volume":"35-2","author":"M. Solomon","year":"1987","unstructured":"M. Solomon, Algorithms for the vehicle routing and scheduling problem with time window constraints, Operations Research, 35-2 (1987), pp. 254\u2013265.","journal-title":"Operations Research"},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.22.1.1","volume":"22","author":"M. Solomon","year":"1988","unstructured":"M. Solomon and J. Desrosiers, Time window constrained routing and scheduling problems: a survey, Transportation Science, 22 (1988), pp. 1\u201313.","journal-title":"Transportation Science"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:51Z","timestamp":1605647931000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}