{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T12:45:02Z","timestamp":1751287502333,"version":"3.41.0"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819683116","type":"print"},{"value":"9789819683123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-8312-3_4","type":"book-chapter","created":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T10:14:49Z","timestamp":1751192089000},"page":"49-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity Classes for\u00a0Online Problems with\u00a0and\u00a0Without 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":[[2025,6,30]]},"reference":[{"key":"4_CR1","unstructured":"Algorithms with predictions. https:\/\/algorithms-with-predictions.github.io\/. Accessed 28 Mar 2025"},{"key":"4_CR2","unstructured":"Antoniadis, A., et al.: Paging with succinct predictions. In: 40th International Conference on Machine Learning (ICML), vol. 202, pp. 952\u2013968. PMLR (2023)"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: , Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"4_CR4","unstructured":"Berg, M.: Comparing the hardness of online minimization and maximization problems with predictions. In: International Joint Conference on Theoretical Computer Science - Frontier of Algorithmic Wisdom (IJTCS-FAW). Lecture Notes in Computer Science. Springer (2025). Accepted for publication. arXiv:2409.12694"},{"key":"4_CR5","unstructured":"Berg, M., Boyar, J., Favrholdt, L.M., Larsen, K.S.: Complexity classes for online problems with and without predictions (2024). arXiv:2406.18265"},{"key":"4_CR6","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. Theoret. Comput. Sci. 554, 95\u2013108 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.06.006","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR7","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. 5878, pp. 331\u2013340. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_35"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00224-019-09955-7","volume":"64","author":"A Borodin","year":"2020","unstructured":"Borodin, A., Boyar, J., Larsen, K.S., Pankratov, D.: Advice complexity of priority algorithms. Theory Comput. Syst. 64, 593\u2013625 (2020). https:\/\/doi.org\/10.1007\/s00224-019-09955-7","journal-title":"Theory Comput. Syst."},{"key":"4_CR9","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"issue":"5","key":"4_CR10","doi-asserted-by":"publisher","first-page":"1938","DOI":"10.1007\/s00453-018-0519-1","volume":"81","author":"J Boyar","year":"2019","unstructured":"Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrb\u010d\u00edk, M., Larsen, K.S.: Online dominating set. Algorithmica 81(5), 1938\u20131964 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0519-1","journal-title":"Algorithmica"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1007\/s00224-016-9688-y","volume":"61","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: The advice complexity of a class of hard online problems. Theory Comput. Syst. 61, 1128\u20131177 (2017). https:\/\/doi.org\/10.1007\/s00224-016-9688-y","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.dam.2006.04.039","volume":"155","author":"M Chleb\u00edk","year":"2007","unstructured":"Chleb\u00edk, M., Chleb\u00edkova, J.: On approxmiation hardness of the minimum 2SAT-deletion problem. Discret. Appl. Math. 155(2), 172\u2013179 (2007). https:\/\/doi.org\/10.1016\/j.dam.2006.04.039","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"4_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theoret. Comput. Sci. 332(1\u20133), 83\u2013108 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2004.08.015","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005). https:\/\/doi.org\/10.4007\/annals.2005.162.439","journal-title":"Ann. Math."},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovic, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO Theor. Inform. Appl. 43(3), 585\u2013613 (2009). https:\/\/doi.org\/10.1051\/ita\/2009012","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"4_CR16","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"24","key":"4_CR17","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. Theoret. Comput. Sci. 412(24), 2642\u20132656 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.08.007","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR18","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. (1990)"},{"key":"4_CR19","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Saha, B., Seybold, M.P., Ye, C.: On the complexity of algorithms with predictions for dynamic graph problems. In: 15th Innovations in Theoretical Computer Science Conference (ITCS). Leibniz International Proceedings in Informatics (LIPIcs), vol. 287, pp. 62:1\u201362:25. Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.62","DOI":"10.4230\/LIPIcs.ITCS.2024.62"},{"key":"4_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. 6281, pp. 24\u201336. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_3"},{"key":"4_CR21","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"4_CR22","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Addison-Wesley Longman Publishing Co., Inc. (2005)"},{"key":"4_CR23","doi-asserted-by":"publisher","unstructured":"Komm, D.: An Introduction to Online Computation: Determinism, Randomization, Advice. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2","DOI":"10.1007\/978-3-319-42749-2"},{"issue":"2","key":"4_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: maxsat and maxcut. J. Algorithms 31(2), 335\u2013354 (1999). https:\/\/doi.org\/10.1006\/jagm.1998.0996","journal-title":"J. Algorithms"},{"key":"4_CR25","unstructured":"Mikkelsen, J.W.: Randomization can be as helpful as a glimpse of the future in online computation (2015). arXiv:1511.05886"},{"key":"4_CR26","doi-asserted-by":"publisher","unstructured":"Mikkelsen, J.W.: Randomization can be as helpful as a glimpse of the future in online computation. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a055, pp. 39:1\u201339:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.39","DOI":"10.4230\/LIPIcs.ICALP.2016.39"},{"issue":"3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991). https:\/\/doi.org\/10.1016\/0022-0000(91)90023-X","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"4_CR28","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233\u2013235 (1982). https:\/\/doi.org\/10.1016\/0020-0190(82)90022-9","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"4_CR29","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). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-8312-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T10:15:01Z","timestamp":1751192101000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-8312-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819683116","9789819683123"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-8312-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"30 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ijtcs-faw.github.io\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}