{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:25:29Z","timestamp":1775791529056,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319252575","type":"print"},{"value":"9783319252582","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_23","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T03:10:18Z","timestamp":1445224218000},"page":"328-341","source":"Crossref","is-referenced-by-count":13,"title":["Treasure Hunt with Advice"],"prefix":"10.1007","author":[{"given":"Dennis","family":"Komm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasmin","family":"Smula","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"issue":"2","key":"23_CR1","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R.A. Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Information and Computation\u00a0106(2), 234\u2013252 (1993)","journal-title":"Information and Computation"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BFb0029571","volume-title":"Online Algorithms","author":"P. Berman","year":"1998","unstructured":"Berman, P.: On-line searching and navigation. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol.\u00a01442, pp. 232\u2013241. Springer, Heidelberg (1998)"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"H.-J. B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theoretical Computer Science\u00a0554, 95\u2013108 (2014)","journal-title":"Theoretical Computer Science"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-10631-6_35","volume-title":"Algorithms and Computation","author":"H.-J. B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"H.-J. B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-29344-3_6","volume-title":"LATIN 2012: Theoretical Informatics","author":"H.-J. B\u00f6ckenhauer","year":"2012","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: On the advice complexity of the knapsack problem. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 61\u201372. Springer, Heidelberg (2012)"},{"key":"23_CR7","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: Advice complexity for a class of online problems. In: Mayr, E.W., Ollinger, N. (eds.) Proc.\u00a0of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). LIPIcs, vol.\u00a030, pp. 116\u2013129. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015)"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-31104-8_23","volume-title":"Structural Information and Communication Complexity","author":"S. Dobrev","year":"2012","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 267\u2013278. Springer, Heidelberg (2012)"},{"issue":"3","key":"23_CR9","first-page":"585","volume":"43","author":"S. Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO ITA\u00a043(3), 585\u2013613 (2009)","journal-title":"RAIRO ITA"},{"issue":"24","key":"23_CR10","doi-asserted-by":"publisher","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y. Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theoretical Computer Science\u00a0412(24), 2642\u20132656 (2011)","journal-title":"Theoretical Computer Science"},{"key":"23_CR11","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8, 128\u2013140 (1736)"},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-33651-5_5","volume-title":"Distributed Computing","author":"O. Feinerman","year":"2012","unstructured":"Feinerman, O., Korman, A.: Memory lower bounds for randomized collaborative search and implications for biology. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol.\u00a07611, pp. 61\u201375. Springer, Heidelberg (2012)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Kowalski, D., Panconesi, A. (eds.) Proc. of the 31st ACM Symposium on Principles of Distributed Computing (PODC 2012), pp. 77\u201386 (2012)","DOI":"10.1145\/2332432.2332444"},{"issue":"2","key":"23_CR14","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1137\/S0097539795279943","volume":"28","author":"A. Fiat","year":"1998","unstructured":"Fiat, A., Foster, D.P., Karloff, H.J., Rabani, Y., Ravid, Y., Vishwanathan, S.: Competitive algorithms for layered graph traversal. SIAM Journal on Computing\u00a028(2), 447\u2013462 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-35476-2_11","volume-title":"Principles of Distributed Systems","author":"K.-T. F\u00f6rster","year":"2012","unstructured":"F\u00f6rster, K.-T., Wattenhofer, R.: Directed graph exploration. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol.\u00a07702, pp. 151\u2013165. Springer, Heidelberg (2012)"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: A new measure of difficulty for communication tasks. In: Proc. of the 25th Annual ACM symposium on Principles of distributed computing (PODC 2006), pp. 179\u2013187. ACM (2006)","DOI":"10.1145\/1146381.1146410"},{"issue":"3\u20134","key":"23_CR17","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/j.jcss.2009.07.002","volume":"76","author":"P. Fraigniaud","year":"2010","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. Journal of Computer and System Sciences\u00a076(3\u20134), 222\u2013232 (2010)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"23_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cosrev.2010.05.001","volume":"4","author":"S.K. Ghosh","year":"2010","unstructured":"Ghosh, S.K., Klein, R.: Online algorithms for searching and exploration in the plane. Computer Science Review\u00a04(4), 189\u2013201 (2010)","journal-title":"Computer Science Review"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-319-03578-9_5","volume-title":"Structural Information and Communication Complexity","author":"S. Gupta","year":"2013","unstructured":"Gupta, S., Kamali, S., L\u00f3pez-Ortiz, A.: On advice complexity of the k-server problem under sparse metrics. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol.\u00a08179, pp. 55\u201367. Springer, Heidelberg (2013)"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J. Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 24\u201336. Springer, Heidelberg (2010)"},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(94)90155-4","volume":"130","author":"B. Kalyanasundaram","year":"1994","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: Constructing competitive tours from local information. Theoretical Computer Science\u00a0130(1), 125\u2013138 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"23_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M.-Y. Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation\u00a0131(1), 63\u201379 (1996)","journal-title":"Information and Computation"},{"issue":"2","key":"23_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/978-3-319-14472-6_18","volume-title":"Principles of Distributed Systems","author":"A. Miller","year":"2014","unstructured":"Miller, A., Pelc, A.: Tradeoffs between cost and information for rendezvous and treasure hunt. In: Aguilera, M.K., Querzoni, L., Shapiro, M. (eds.) OPODIS 2014. LNCS, vol.\u00a08878, pp. 263\u2013276. Springer, Heidelberg (2014)"},{"key":"23_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-662-46018-4_5","volume-title":"Algorithms for Sensor Systems","author":"A. Miller","year":"2015","unstructured":"Miller, A., Pelc, A.: Fast rendezvous with advice. In: Gao, J., Efrat, A., Fekete, S.P., Zhang, Y. (eds.) ALGOSENSORS 2014, LNCS 8847. LNCS, vol.\u00a08847, pp. 75\u201387. Springer, Heidelberg (2015)"},{"issue":"1","key":"23_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theoretical Computer Science\u00a084(1), 127\u2013150 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"23_CR27","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.J. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing\u00a06(3), 563\u2013581 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-642-29116-6_17","volume-title":"Approximation and Online Algorithms","author":"M.P. Renault","year":"2012","unstructured":"Renault, M.P., Ros\u00e9n, A.: On online algorithms with advice for the k-server problem. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol.\u00a07164, pp. 198\u2013210. Springer, Heidelberg (2012)"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms 10(3), 12:1\u201312:15 (2012)","DOI":"10.1145\/2601068"},{"key":"23_CR30","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: Proc. of the 18th Annual Symposium on Foundations of Computer Science (FOCS 1977), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T03:44:13Z","timestamp":1559274253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}