{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T14:08:24Z","timestamp":1749046104549,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"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-38906-1_10","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"136-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Minimum Spanning Trees with Weight Predictions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8637-7113","authenticated-orcid":false,"given":"Magnus","family":"Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0725-8341","authenticated-orcid":false,"given":"Joan","family":"Boyar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3054-2997","authenticated-orcid":false,"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"10_CR1","unstructured":"Algorithms with Predictions. https:\/\/algorithms-with-predictions.github.io\/. Accessed 14 Feb 2023"},{"key":"10_CR2","unstructured":"Berg, M., Boyar, J., Favrholdt, L.M., Larsen, K.S.: Online minimum spanning trees with weight predictions (2023). arXiv:2302.12029"},{"issue":"4","key":"10_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1142\/S0129054118410034","volume":"29","author":"MP Bianchi","year":"2018","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H., Br\u00fclisauer, T., Komm, D., Palano, B.: Online minimum spanning tree with advice. Int. J. Found. Comput. Sci. 29(4), 505\u2013527 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 50(2), 1\u201334 (2017). Article No. 19","DOI":"10.1145\/3056461"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: Relative worst-order analysis: a survey. ACM Computing Surv. 54(1), 1\u201321 (2020). Article No. 8","DOI":"10.1145\/3425910"},{"issue":"4","key":"10_CR6","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-014-9884-6","volume":"72","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. Algorithmica 72(4), 969\u2013994 (2015)","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR7","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","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 - Theor. Inform. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO - Theor. Inform. Appl."},{"issue":"3","key":"10_CR8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"issue":"24","key":"10_CR9","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. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1017\/9781108637435.015","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"A Gupta","year":"2020","unstructured":"Gupta, A., Singla, S.: Random-order models. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 234\u2013258. Columbia University, New York (2020)"},{"key":"10_CR11","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. 6281, pp. 24\u201336. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_3"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Im, S., Kumar, R., Qaem, M.M., Purohit, M.: Non-clairvoyant scheduling with predictions. In: 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 285\u2013294. ACM (2021)","DOI":"10.1145\/3409964.3461790"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 77\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"10_CR14","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013364. SIAM (1996)"},{"key":"10_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2","volume-title":"An Introduction to Online Computation: Determinism, Randomization, Advice","author":"D Komm","year":"2016","unstructured":"Komm, D.: An Introduction to Online Computation: Determinism, Randomization, Advice. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2"},{"issue":"4","key":"10_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3447579","volume":"68","author":"T Lykouris","year":"2021","unstructured":"Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. J. ACM 68(4), 1\u201325 (2021)","journal-title":"J. ACM"},{"issue":"7","key":"10_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3528087","volume":"65","author":"M Mitzenmacher","year":"2022","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. Commun. ACM 65(7), 33\u201335 (2022)","journal-title":"Commun. ACM"},{"issue":"2","key":"10_CR18","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"10_CR19","unstructured":"West, D.B.: Introduction to Graph Theory. Featured Titles for Graph Theory, 2nd edn. Prentice Hall, Hoboken (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:06:16Z","timestamp":1690473976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_10","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":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","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":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","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":"47","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":"51% - 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.1","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":"10","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)"}}]}}