{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:15:02Z","timestamp":1759335302401,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031183669"},{"type":"electronic","value":"9783031183676"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-18367-6_7","type":"book-chapter","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T16:05:36Z","timestamp":1666281936000},"page":"134-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Power of\u00a0Amortized Recourse for\u00a0Online Graph Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0194-9360","authenticated-orcid":false,"given":"Alison Hsiang-Hsuan","family":"Liu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3234-4564","authenticated-orcid":false,"given":"Jonathan","family":"Toole-Charignon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Albers, S., Schraink, S.: Tight bounds for online coloring of basic graph classes. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms, ESA 2017, 4\u20136 September 2017, Vienna, Austria. LIPIcs, vol. 87, pp. 7:1\u20137:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.7","key":"7_CR1","DOI":"10.4230\/LIPIcs.ESA.2017.7"},{"issue":"4","key":"7_CR2","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1007\/s10878-020-00641-w","volume":"40","author":"S Angelopoulos","year":"2020","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S.: Online maximum matching with recourse. J. Comb. Optim. 40(4), 974\u20131007 (2020). https:\/\/doi.org\/10.1007\/s10878-020-00641-w","journal-title":"J. Comb. Optim."},{"issue":"3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.ipl.2012.09.011","volume":"113","author":"T Avitabile","year":"2013","unstructured":"Avitabile, T., Mathieu, C., Parkinson, L.H.: Online constrained optimization with recourse. Inf. Process. Lett. 113(3), 81\u201386 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2012.09.011","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In: Naor, J.S., Buchbinder, N. (eds.) Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, Alexandria, VA, USA, 9\u201312 January 2022, pp. 35\u201366. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.3","key":"7_CR4","DOI":"10.1137\/1.9781611977073.3"},{"doi-asserted-by":"publisher","unstructured":"Azar, Y., Touitou, N.: Beyond tree embeddings - a deterministic framework for network design with deadlines or delay. In: Irani [18], pp. 1368\u20131379 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00129","key":"7_CR5","DOI":"10.1109\/FOCS46700.2020.00129"},{"doi-asserted-by":"publisher","unstructured":"Bernstein, A., Holm, J., Rotenberg, E.: Online bipartite matching with amortized $$O$$(log $${}^{{2}}$$ n) replacements. J. ACM 66(5), 37:1\u201337:23 (2019). https:\/\/doi.org\/10.1145\/3344999","key":"7_CR6","DOI":"10.1145\/3344999"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-030-04693-4_4","volume-title":"Approximation and Online Algorithms","author":"M Bienkowski","year":"2018","unstructured":"Bienkowski, M., Kraska, A., Liu, H.-H., Schmidt, P.: A primal-dual online deterministic algorithm for matching with delays. In: Epstein, L., Erlebach, T. (eds.) WAOA 2018. LNCS, vol. 11312, pp. 51\u201368. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04693-4_4"},{"issue":"2","key":"7_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"RB Boppana","year":"1992","unstructured":"Boppana, R.B., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT 32(2), 180\u2013196 (1992). https:\/\/doi.org\/10.1007\/BF01994876","journal-title":"BIT"},{"doi-asserted-by":"publisher","unstructured":"Bosek, B., Disser, Y., Feldmann, A.E., Pawlewicz, J., Zych-Pawlewicz, A.: Recoloring interval graphs with limited recourse budget. In: Albers, S. (ed.) 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, 22\u201324 June 2020, T\u00f3rshavn, Faroe Islands. LIPIcs, vol. 162, pp. 17:1\u201317:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2020.17","key":"7_CR9","DOI":"10.4230\/LIPIcs.SWAT.2020.17"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1007\/s00453-022-00944-w","volume":"84","author":"J Boyar","year":"2022","unstructured":"Boyar, J., Favrholdt, L.M., Kotrbc\u00edk, M., Larsen, K.S.: Relaxing the irrevocability requirement for online graph algorithms. Algorithmica 84, 1916\u20131951 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00944-w","journal-title":"Algorithmica"},{"doi-asserted-by":"publisher","unstructured":"Cygan, M., Czumaj, A., Mucha, M., Sankowski, P.: Online facility location with deletions. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, ESA 2018, 20\u201322 August 2018, Helsinki, Finland. LIPIcs, vol. 112, pp. 21:1\u201321:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.21","key":"7_CR11","DOI":"10.4230\/LIPIcs.ESA.2018.21"},{"issue":"1","key":"7_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955276","volume":"45","author":"A Gu","year":"2016","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: Maintaining a constant-competitive steiner tree online. SIAM J. Comput. 45(1), 1\u201328 (2016). https:\/\/doi.org\/10.1137\/140955276","journal-title":"SIAM J. Comput."},{"unstructured":"Gupta, A., Guruganesh, G., Kumar, A., Wajc, D.: Fully-dynamic bin packing with limited repacking. CoRR abs\/1711.02078 (2017). http:\/\/arxiv.org\/abs\/1711.02078","key":"7_CR13"},{"doi-asserted-by":"publisher","unstructured":"Gupta, A., Levin, R.: Fully-dynamic submodular cover with bounded recourse. In: Irani [18], pp. 1147\u20131157 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00110","key":"7_CR14","DOI":"10.1109\/FOCS46700.2020.00110"},{"issue":"5","key":"7_CR15","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608\u20131623 (2002). https:\/\/doi.org\/10.1137\/S0097539700381097","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Harutyunyan, H.A., Pankratov, D., Racicot, J.: Online domination: the value of getting to know all your neighbors. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, 23\u201327 August 2021, Tallinn, Estonia. LIPIcs, vol. 202, pp. 57:1\u201357:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.57","key":"7_CR16","DOI":"10.4230\/LIPIcs.MFCS.2021.57"},{"issue":"4","key":"7_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$${}^{\\text{5\/2 }}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Irani, S. (ed.): 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020","key":"7_CR18","DOI":"10.1109\/FOCS46700.2020"},{"doi-asserted-by":"publisher","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms 5(4), 41:1\u201341:8 (2009). https:\/\/doi.org\/10.1145\/1597036.1597045","key":"7_CR19","DOI":"10.1145\/1597036.1597045"},{"doi-asserted-by":"publisher","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019","key":"7_CR20","DOI":"10.1016\/j.jcss.2007.06.019"},{"doi-asserted-by":"publisher","unstructured":"Megow, N., N\u00f6lke, L.: Online minimum cost matching with recourse on the line. In: Byrka, J., Meka, R. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, 17\u201319 August 2020, Virtual Conference. LIPIcs, vol. 176, pp. 37:1\u201337:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.37","key":"7_CR21","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.37"},{"issue":"3","key":"7_CR22","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/130917703","volume":"45","author":"N Megow","year":"2016","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. SIAM J. Comput. 45(3), 859\u2013880 (2016). https:\/\/doi.org\/10.1137\/130917703","journal-title":"SIAM J. Comput."},{"issue":"1","key":"7_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform. 22(1), 115\u2013123 (1985). https:\/\/doi.org\/10.1007\/BF00290149","journal-title":"Acta Inform."},{"key":"7_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1007\/978-3-662-47672-7_87","volume-title":"Automata, Languages, and Programming","author":"Y Wang","year":"2015","unstructured":"Wang, Y., Wong, S.C.: Two-sided online bipartite matching and vertex cover: beating the greedy algorithm. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part I. LNCS, vol. 9134, pp. 1070\u20131081. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_87"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-18367-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T16:06:09Z","timestamp":1666281969000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-18367-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031183669","9783031183676"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-18367-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Potsdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2022.eu\/waoa\/","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":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","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":"12","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":"57% - 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","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":"3","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)"}}]}}