{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T19:23:47Z","timestamp":1768591427547,"version":"3.49.0"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032067050","type":"print"},{"value":"9783032067067","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-06706-7_10","type":"book-chapter","created":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T23:55:39Z","timestamp":1759276539000},"page":"142-156","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Low Recourse Arborescence Forests Under Uniformly Random Arcs"],"prefix":"10.1007","author":[{"given":"J.","family":"Niklas Dahlmeier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. Ellis","family":"Hershkowitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,1]]},"reference":[{"issue":"4","key":"10_CR1","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":"5","key":"10_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3450349","volume":"68","author":"C Argue","year":"2021","unstructured":"Argue, C., Gupta, A., Tang, Z., Guruganesh, G.: Chasing convex bodies with linear competitive ratio. J. ACM (JACM) 68(5), 1\u201310 (2021)","journal-title":"J. ACM (JACM)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bansa, N., B\u00f6hm, M., Eli\u00e1\u0161, M., Koumoutsos, G., Umboh, S.W.: Nested convex bodies are chaseable. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1253\u20131260 (2018)","DOI":"10.1137\/1.9781611975031.81"},{"key":"10_CR4","unstructured":"B\u00e9rczi, K., Frank, A.: Packing arborescences (2009)"},{"key":"10_CR5","unstructured":"Bernstein, A., Dudeja, A.: Online matching with recourse: random edge arrivals. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2020)"},{"issue":"5","key":"10_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3344999","volume":"66","author":"A Bernstein","year":"2019","unstructured":"Bernstein, A., Holm, J., Rotenberg, E.: Online bipartite matching with amortized $$\\text{ O }(log^2 n)$$ replacements. J. ACM (JACM) 66(5), 1\u201323 (2019)","journal-title":"J. ACM (JACM)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Hariharan, R., Kavitha, T., Panigrahi, D.: Fast edge splitting and edmonds\u2019 arborescence construction for unweighted graphs. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 455\u2013464 (2008)","DOI":"10.1137\/1.9781611973068.30"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Buchbinder, N., Levin, R., Saranurak, T.: Chasing positive bodies. In: Symposium on Foundations of Computer Science (FOCS) (2023)","DOI":"10.1109\/FOCS57990.2023.00103"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: Symposium on Foundations of Computer Science (FOCS), pp. 384\u2013393 (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Gupta, A., Hathcock, D., Karlin, A.R., Sarkar, S.: Maintaining matroid intersections online. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4283\u20134304 (2024)","DOI":"10.1137\/1.9781611977912.149"},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: INFOCOM, pp. 1044\u20131052 (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"key":"10_CR13","first-page":"1396","volume":"14","author":"YJ Chu","year":"1965","unstructured":"Chu, Y.J.: On the shortest arborescence of a directed graph. Sci. Sinica 14, 1396\u20131400 (1965)","journal-title":"Sci. Sinica"},{"key":"10_CR14","unstructured":"Cohen-Addad, V., Hjuler, N.O.D., Parotsidis, N., Saulpic, D., Schwiegelshohn, C.: Fully dynamic consistent facility location. In: Annual Conference on Neural Information Processing Systems (NeurIPS), vol. 32 (2019)"},{"issue":"4","key":"10_CR15","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1137\/0215066","volume":"15","author":"WH Cunningham","year":"1986","unstructured":"Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15(4), 948\u2013957 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1798596.1798599","volume":"6","author":"M Drescher","year":"2010","unstructured":"Drescher, M., Vetta, A.: An approximation algorithm for the maximum leaf spanning arborescence problem. ACM Trans. Algorithms (TALG) 6(3), 1\u201318 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J., et al.: Optimum branchings. J. Res. Natl. Bur. Stand. B 71(4), 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Epasto, A., Lattanzi, S., Sozio, M.: Efficient densest subgraph computation in evolving graphs. In: International World Wide Web Conference (WWW), pp. 300\u2013310 (2015)","DOI":"10.1145\/2736277.2741638"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Fichtenberger, H., Lattanzi, S., Norouzi-Fard, A., Svensson, O.: Consistent $$k$$-clustering for general metrics. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2660\u20132678. SIAM (2021)","DOI":"10.1137\/1.9781611976465.158"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to Random Graphs. Cambridge University Press (2015)","DOI":"10.1017\/CBO9781316339831"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: Annual ACM Symposium on Theory of Computing (STOC), pp. 112\u2013122 (1991)","DOI":"10.1145\/103418.103436"},{"issue":"2","key":"10_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-60220-8_62","volume-title":"Algorithms and data structures","author":"EF Grove","year":"1995","unstructured":"Grove, E.F., Kao, M.-Y., Krishnan, P., Vitter, J.S.: Online perfect matching and mobile computing. In: Akl, S.G., Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 194\u2013205. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60220-8_62"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive steiner tree online. In: Annual ACM Symposium on Theory of Computing (STOC), pp. 525\u2013534 (2013)","DOI":"10.1145\/2488608.2488674"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Panigrahi, D.: Online and dynamic algorithms for set cover. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 537\u2013550 (2017)","DOI":"10.1145\/3055399.3055493"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Online steiner tree with deletions. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 455\u2013467 (2014)","DOI":"10.1137\/1.9781611973402.34"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: matching, scheduling, and flows. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 468\u2013479 (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Gupta, A., Levin, R.: Fully-dynamic submodular cover with bounded recourse. In: Symposium on Foundations of Computer Science (FOCS), pp. 1147\u20131157 (2020)","DOI":"10.1109\/FOCS46700.2020.00110"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Lincoln, A., Saha, B.: The complexity of average-case dynamic subgraph counting. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 459\u2013498. SIAM (2022)","DOI":"10.1137\/1.9781611977073.23"},{"issue":"3","key":"10_CR30","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic steiner tree problem. SIAM J. Discret. Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"10_CR31","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"RM Karp","year":"1990","unstructured":"Karp, R.M.: The transitive closure of a random digraph. Random Structures & Algorithms 1(1), 73\u201393 (1990)","journal-title":"Random Structures & Algorithms"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Korte, B., Vygen, J., Korte, B., Vygen, J.: Spanning trees and arborescences. Combinatorial Optimization: Theory and Algorithms, pp. 133\u2013157 (2018)","DOI":"10.1007\/978-3-662-56039-6_6"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Li, S., Suriyanarayana, V.: Online unrelated-machine load balancing and generalized flow with recourse. In: Annual ACM Symposium on Theory of Computing (STOC), pp. 775\u2013788 (2023)","DOI":"10.1145\/3564246.3585222"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Lacki, J., Haeupler, B., Grunau, C., Jayaram, R., Rozho\u0148, V.: Fully dynamic consistent k-center clustering. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3463\u20133484 (2024)","DOI":"10.1137\/1.9781611977912.124"},{"key":"10_CR35","doi-asserted-by":"crossref","unstructured":"Laekhanukit, B., Oveis\u00a0Gharan, S., Singh, M.: A rounding by sampling approach to the minimum size k-arc connected subgraph problem. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 606\u2013616 (2012)","DOI":"10.1007\/978-3-642-31594-7_51"},{"key":"10_CR36","unstructured":"Lattanzi, S., Vassilvitskii, S.: Consistent k-clustering. In: International Conference on Machine Learning (ICML), pp. 1975\u20131984 (2017)"},{"key":"10_CR37","unstructured":"Megow, N., N\u00f6lke, L.: Online minimum cost matching on the line with recourse. arXiv preprint arXiv:2001.03107 (2020)"},{"issue":"3","key":"10_CR38","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)","journal-title":"SIAM J. Comput."},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"Sellke, M.: Chasing convex bodies optimally. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1509\u20131518 (2020)","DOI":"10.1137\/1.9781611975994.92"}],"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-032-06706-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T07:07:06Z","timestamp":1768547226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06706-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,1]]},"ISBN":["9783032067050","9783032067067"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06706-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,1]]},"assertion":[{"value":"1 October 2025","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":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","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":"18 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","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":"waoa2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2025\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}