{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:26:44Z","timestamp":1778732804625,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,10,26]],"date-time":"2015-10-26T00:00:00Z","timestamp":1445817600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00224-015-9664-y","type":"journal-article","created":{"date-parts":[[2015,10,26]],"date-time":"2015-10-26T06:20:31Z","timestamp":1445840431000},"page":"112-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The Update Complexity of Selection and Related Problems"],"prefix":"10.1007","volume":"59","author":[{"given":"Manoj","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yogish","family":"Sabharwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,26]]},"reference":[{"issue":"5","key":"9664_CR1","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1109\/TKDE.2008.190","volume":"21","author":"CC Aggarwal","year":"2009","unstructured":"Aggarwal, C.C., Philip, S.Y.: A survey of uncertain data algorithms and applications. IEEE Trans. Knowl. Data Eng. 21(5), 609\u2013623 (2009)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"9664_CR2","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/S0167-6377(03)00058-0","volume":"32","author":"ID Aron","year":"2004","unstructured":"Aron, I.D., Hentenryck, P.V.: On the complexity of the robust spanning tree problem with interval data. Oper. Res. Lett. 32(1), 36\u201340 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"12","key":"9664_CR3","doi-asserted-by":"crossref","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Z Beerliova","year":"2006","unstructured":"Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal\u00e1k, M., Shankar Ram, L.: Network discovery and verification. IEEE Journal on Selected Areas in Communications 24(12), 2168\u20132181 (2006)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"issue":"4","key":"9664_CR4","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-004-1180-4","volume":"38","author":"R Bruce","year":"2005","unstructured":"Bruce, R., Hoffmann, M., Krizanc, D., Raman, R.: Efficient update strategies for geometric computing with uncertainty. Theory Comput. Syst. 38(4), 411\u2013423 (2005)","journal-title":"Theory Comput. Syst."},{"key":"9664_CR5","doi-asserted-by":"crossref","unstructured":"Feder, T., Motwani, R., O\u2019Callaghan, L., Olston, C., Panigrahy, R.: Computing shortest paths with uncertainty. In: STACS, 367\u2013378 (2003)","DOI":"10.1007\/3-540-36494-3_33"},{"issue":"2","key":"9664_CR6","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1137\/S0097539701395668","volume":"32","author":"T Feder","year":"2003","unstructured":"Feder, T., Motwani, R., Panigrahy, R., Olston, C., Widom, J.: Computing the median with uncertainty. SIAM J. Comput. 32(2), 538\u2013547 (2003)","journal-title":"SIAM J. Comput."},{"key":"9664_CR7","doi-asserted-by":"crossref","unstructured":"Goel, A., Guha, S., Munagala, K.: Asking the right questions: model-driven optimization using probes. In: PODS, 203\u2013212 (2006)","DOI":"10.1145\/1142351.1142380"},{"key":"9664_CR8","unstructured":"Guha, S., Munagala, K.: Model-driven optimization using adaptive probes. In: SODA, 308\u2013317 (2007)"},{"key":"9664_CR9","unstructured":"Gupta, M., Sabharwal, Y., Sen, S.: The update complexity of selection and related problems. In: FSTTCS, 325\u2013338 (2011)"},{"key":"9664_CR10","unstructured":"Hoffmann, M., Erlebach, T., Krizanc, D., Mihal\u00e1k, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: STACS, 277\u2013288 (2008)"},{"key":"9664_CR11","doi-asserted-by":"crossref","unstructured":"Kahan, S.: A model for data in motion. In: STOC, 267\u2013277 (1991)","DOI":"10.1145\/103418.103449"},{"issue":"5","key":"9664_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.ipl.2005.11.001","volume":"97","author":"A Kasperski","year":"2006","unstructured":"Kasperski, A., Zielenski, P.: An approximation algorithm for interval data minmax regret combinatorial optimization problem. Inf. Process. Lett. 97(5), 177\u2013180 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9664_CR13","doi-asserted-by":"crossref","unstructured":"Khanna, S., Tan, W.C.: On computing functions with uncertainty. In: PODS, 171\u2013182 (2001)","DOI":"10.1145\/375551.375577"},{"key":"9664_CR14","unstructured":"Olston, C., Widom, J.: Offering a precision-performance tradeoff for aggregation queries over replicated data. In: VLDB, 144\u2013155 (2000)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9664-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9664-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9664-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:28Z","timestamp":1558698868000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9664-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,26]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9664"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9664-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,26]]}}}