{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:46:49Z","timestamp":1743133609299,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031434204"},{"type":"electronic","value":"9783031434211"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43421-1_20","type":"book-chapter","created":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T20:37:24Z","timestamp":1694983044000},"page":"333-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online State Exploration: Competitive Worst Case and\u00a0Learning-Augmented Algorithms"],"prefix":"10.1007","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyang","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruilong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,18]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Ai, L., Wu, X., Huang, L., Huang, L., Tang, P., Li, J.: The multi-shop ski rental problem. In: SIGMETRICS. pp. 463\u2013475. ACM (2014)","DOI":"10.1145\/2637364.2591984"},{"key":"20_CR2","unstructured":"Anand, K., Ge, R., Kumar, A., Panigrahi, D.: A regression approach to learning-augmented online algorithms. In: NeurIPS, vol. 34 (2021)"},{"key":"20_CR3","unstructured":"Anand, K., Ge, R., Panigrahi, D.: Customizing ML predictions for online algorithms. In: ICML. Proceedings of Machine Learning Research, vol. 119, pp. 303\u2013313. PMLR (2020)"},{"key":"20_CR4","unstructured":"Angelopoulos, S.: Online search with a hint. In: ITCS. LIPIcs, vol. 185, pp. 51:1\u201351:16 (2021)"},{"key":"20_CR5","unstructured":"Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. In: NeurIPS (2020)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/BFb0029569","volume-title":"Online Algorithms","author":"Y Azar","year":"1998","unstructured":"Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 178\u2013195. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029569"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"RA Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"key":"20_CR8","unstructured":"Bamas, \u00c9., Maggiori, A., Svensson, O.: The primal-dual method for learning augmented algorithms. In: NeurIPS (2020)"},{"issue":"6","key":"20_CR9","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"20_CR10","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s00453-007-9005-x","volume":"50","author":"M Chrobak","year":"2008","unstructured":"Chrobak, M., Kenyon, C., Noga, J., Young, N.E.: Incremental medians via online bidding. Algorithmica 50(4), 455\u2013478 (2008)","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"20_CR11","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361(2\u20133), 342\u2013355 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"D\u00fctting, P., Lattanzi, S., Leme, R.P., Vassilvitskii, S.: Secretaries with advice. In: EC, pp. 409\u2013429. ACM (2021)","DOI":"10.1145\/3465456.3467623"},{"issue":"12\u201313","key":"20_CR13","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.ipl.2010.03.016","volume":"110","author":"L Epstein","year":"2010","unstructured":"Epstein, L., Levin, A.: Randomized algorithms for online bounded bidding. Inf. Process. Lett. 110(12\u201313), 503\u2013506 (2010)","journal-title":"Inf. Process. Lett."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. In: SPAA, pp. 285\u2013294. ACM (2021)","DOI":"10.1145\/3409964.3461790"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Jiang, Z., Panigrahi, D., Sun, K.: Online algorithms for weighted paging with predictions. In: ICALP, pp. 69:1\u201369:18 (2020)","DOI":"10.1145\/3548774"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0959","volume":"29","author":"M Kao","year":"1998","unstructured":"Kao, M., Ma, Y., Sipser, M., Yin, Y.L.: Optimal constructions of hybrid algorithms. J. Algorithms 29(1), 142\u2013164 (1998)","journal-title":"J. Algorithms"},{"issue":"1","key":"20_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M Kao","year":"1996","unstructured":"Kao, M., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201379 (1996)","journal-title":"Inf. Comput."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: SODA, pp. 1859\u20131877 (2020)","DOI":"10.1137\/1.9781611975994.114"},{"issue":"2","key":"20_CR19","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/100794018","volume":"26","author":"Z Lotker","year":"2012","unstructured":"Lotker, Z., Patt-Shamir, B., Rawitz, D.: Rent, lease, or buy: randomized algorithms for multislope ski rental. SIAM J. Discret. Math. 26(2), 718\u2013736 (2012)","journal-title":"SIAM J. Discret. Math."},{"key":"20_CR20","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: ICML, Proceedings of Machine Learning Research, vol. 80, pp. 3302\u20133311. PMLR (2018)"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: The parking permit problem. In: FOCS, pp. 274\u2013284. IEEE Computer Society (2005)","DOI":"10.1109\/SFCS.2005.72"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In: Beyond the Worst-Case Analysis of Algorithms, pp. 646\u2013662. Cambridge University Press (2020)","DOI":"10.1017\/9781108637435.037"},{"key":"20_CR23","unstructured":"Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: NeurIPS, pp. 9684\u20139693 (2018)"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: SODA, pp. 1834\u20131845 (2020)","DOI":"10.1137\/1.9781611975994.112"},{"key":"20_CR25","unstructured":"Wang, S., Li, J., Wang, S.: Online algorithms for multi-shop ski rental with machine learned advice. In: NeurIPS (2020)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases: Research Track"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43421-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T06:56:29Z","timestamp":1730098589000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43421-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031434204","9783031434211"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43421-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"18 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The current paper is a theoretical work that explores various ideas and concepts related to the topic which aims to strengthen the traditional worst-case algorithm via machine learning advice. As such, there are no ethical issues associated with the research presented here. The paper includes some experiments which aims to verify the efficiency of the proposed algorithms. But this paper does not involve any experiments or studies that involve human and no personal information or data is used in the analysis. Instead, the focus is on developing theoretical models and frameworks that can help to advance our understanding of the subject matter.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Issues"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2023.ecmlpkdd.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"829","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"196","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.63","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Applied Data Science Track: 239 submissions, 58 accepted papers; Demo Track: 31 submissions, 16 accepted papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}