{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:35:59Z","timestamp":1725564959156},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228561"},{"type":"electronic","value":"9783540277989"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27798-9_32","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T23:01:28Z","timestamp":1283727688000},"page":"290-299","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for the On-Line Quota Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"Marc","family":"Demange","sequence":"additional","affiliation":[]},{"given":"Luigi","family":"Laura","sequence":"additional","affiliation":[]},{"given":"Vangelis","family":"Paschos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"32_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"S. Arya","year":"1998","unstructured":"Arya, S., Ramesh, H.: A 2.5-factor approximation algorithm for the k-mst problem. Information Processing Letters\u00a065(3), 117\u2013118 (1998)","journal-title":"Information Processing Letters"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/3-540-46541-3_53","volume-title":"STACS 2000","author":"N. Ascheuer","year":"2000","unstructured":"Ascheuer, N., Krumke, S.O., Rambau, J.: On-line dial-a-ride problems: Minimizing the completion time. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 639\u2013650. Springer, Heidelberg (2000)"},{"issue":"4","key":"32_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/s004530010071","volume":"29","author":"G. Ausiello","year":"1998","unstructured":"Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M.: Algorithms for the on-line travelling salesman. Algorithmica\u00a029(4), 560\u2013581 (1998)","journal-title":"Algorithmica"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, May 1995, pp. 277\u2013283 (1995)","DOI":"10.1145\/225058.225139"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing (1999)","DOI":"10.1137\/S009753979528826X"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E. Balas","year":"1989","unstructured":"Balas, E.: The prize collecting traveling salesman problem. Networks\u00a019, 621\u2013636 (1989)","journal-title":"Networks"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1287\/ijoc.13.2.138.10517","volume":"13","author":"M. Blom","year":"2001","unstructured":"Blom, M., Krumke, S.O., de Paepe, W.E., Stougie, L.: The online-tsp against fair adversaries. INFORMS Journal on Computing\u00a013, 138\u2013148 (2001)","journal-title":"INFORMS Journal on Computing"},{"key":"32_CR8","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS-2003)","author":"A. Blum","year":"2003","unstructured":"Blum, A., Chawla, S., Karger, D., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS-2003), Cambridge, MA, IEEE, Los Alamitos (2003)"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k-mst problem. In: ACM Symposium on Theory of Computing, pp. 442\u2013448 (1996)","DOI":"10.1145\/237814.237992"},{"key":"32_CR10","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge (1998)"},{"key":"32_CR11","unstructured":"Cheung, S.Y., Kumar, A.: Efficient quorumcast routing algorithms. In: Proceedings of INFOCOM 1994, Toronto, vol.\u00a02, pp. 840\u2013855 (1994)"},{"key":"32_CR12","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, G.S.I.A. Carnegie Mellon University (1976)"},{"issue":"1","key":"32_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0304-3975(00)00261-9","volume":"268","author":"E. Feuerstein","year":"2001","unstructured":"Feuerstein, E., Stougie, L.: On-line, single server dial-a-ride problems. Theoretical Computer Science\u00a0268(1), 91\u2013105 (2001)","journal-title":"Theoretical Computer Science"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0029561","volume-title":"Online Algorithms: The State of the Art","author":"A. Fiat","year":"1998","unstructured":"Fiat, A., Woeginger, G.: Dagstuhl Seminar 1996. LNCS, vol.\u00a01442. Springer, Heidelberg (1998)"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3 factor approximation algorithm for the minimum tree spanning k vertices. In: Proceedings IEEE Foundations of Computer Science, pp. 302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-44683-4_43","volume-title":"Mathematical Foundations of Computer Science 2001","author":"S.O. Krumke","year":"2001","unstructured":"Krumke, S.O., de Paepe, W.E., Poensgen, D., Stougie, L.: News from the online traveling repairman. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 487\u2013499. Springer, Heidelberg (2001)"},{"key":"32_CR17","unstructured":"Lipmann, M.: On-Line Routing Problems. PhD thesis, Technische Universiteit Eindhoven (2003)"},{"key":"32_CR18","unstructured":"Regan, A., Irani, S., Lu, X.: On-line algorithms for the dynamic traveling repair problem. In: Proceedings of the 13th Symposium on Discrete Algorithms, pp. 517\u2013524 (2002)"},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/net.3230220305","volume":"22","author":"J.N. Tsitsiklis","year":"1992","unstructured":"Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks\u00a022, 263\u2013282 (1992)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27798-9_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:12Z","timestamp":1605759672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27798-9_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228561","9783540277989"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27798-9_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}