{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T17:38:21Z","timestamp":1780421901083,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540006237","type":"print"},{"value":"9783540364948","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_33","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"367-378","source":"Crossref","is-referenced-by-count":4,"title":["Computing Shortest Paths with Uncertainty"],"prefix":"10.1007","author":[{"given":"T.","family":"Feder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Motwani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L.","family":"O\u2019Callaghan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Olston","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Panigrahy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. \u201cFast estimation of diameter and shortest paths (without matrixm ultiplication).\u201d SIAM Journal on Computing 28(1999):1167\u20131181.","journal-title":"SIAM Journal on Computing"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski. \u201cOn some tighter inapproximability results.\u201d DIMACS Technical Report 99\u201323 (1999).","DOI":"10.1007\/3-540-48523-6_17"},{"key":"33_CR3","unstructured":"X. Deng, T. Kameda, and C. Papadimitriou. \u201cHow to learn an unknown environment.\u201d To appear in the Journal of the ACM."},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom. \u201cComputing the median with uncertainty.\u201d In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pages 602\u2013607.","DOI":"10.1145\/335305.335386"},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF01864160","volume":"4","author":"Z. F\u00fcredi","year":"1988","unstructured":"Z. F\u00fcredi. \u201cMatchings and covers in hypergraphs.\u201d Graphs and Combinatorics 4(1988):115\u2013206.","journal-title":"Graphs and Combinatorics"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"O.H. Ibarra and C.E. Kim. \u201cFast approximation algorithms for the knapsack and sum of subsets problems.\u201d Journal of the ACM 22(1975):463\u2013468.","journal-title":"Journal of the ACM"},{"key":"33_CR7","unstructured":"O. Karasan, M. Pinar, and H. Yaman. \u201cThe robust shortest path problem with interval data.\u201d Manuscript, August 2001."},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"S. Khanna and W. Tan. \u201cOn computing function with uncertainty.\u201d In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001, pages 171\u2013182.","DOI":"10.1145\/375551.375577"},{"key":"33_CR9","first-page":"209","volume":"26","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. \u201cOn minimaxtheorems of combinatorics.\u201d Doctoral Thesis, Mathematikai Lapok 26(1975):209\u2013264. (Hungarian)","journal-title":"On minimaxtheorems of combinatorics"},{"key":"33_CR10","unstructured":"R. Montemanni and L. M. Gambardella. \u201cAn algorithm for the relative robust shortest path problem with interval data.\u201d Tech. Report IDSIA-05-02, 2002."},{"key":"33_CR11","unstructured":"C. Olston and J. Widom. \u201cOffering a precision-performance tradeoff for aggregation queries over replicated data.\u201d In Proceedings of the 26th International Conference on Very Large Data Bases, 2000, pages 144\u2013155."},{"key":"33_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/BFb0035787","volume-title":"Shortest paths without a map","author":"C.H. Papadimitriou","year":"1989","unstructured":"C.H. Papadimitriou and M. Yannakakis. \u201cShortest paths without a map.\u201d In Proceedings of the 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 372(1989):610\u2013620."}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T14:59:26Z","timestamp":1558969166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_33","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}