[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Incremental approximate maximum flow via residual graph sparsification","has_accepted_license":"1","OA_type":"gold","OA_place":"publisher","status":"public","day":"30","month":"06","related_material":{"record":[{"id":"22716","relation":"later_version","status":"public"}]},"corr_author":"1","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"department":[{"_id":"MoHe"}],"oa_version":"Published Version","_id":"21280","ec_funded":1,"abstract":[{"text":"We give an algorithm that, with high probability, maintains a (1-ε)-approximate s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs (m = Ω(n²)), and more generally, for graphs where F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [SICOMP '15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs.","lang":"eng"}],"external_id":{"arxiv":["2502.09105"]},"alternative_title":["LIPIcs"],"intvolume":"       334","quality_controlled":"1","date_updated":"2026-08-20T06:28:00Z","publication":"52nd International Colloquium on Automata, Languages, and Programming","date_published":"2025-06-30T00:00:00Z","doi":"10.4230/lipics.icalp.2025.91","fulldoi":"https://doi.org/10.4230/lipics.icalp.2025.91","article_processing_charge":"No","scopus_import":"1","year":"2025","date_created":"2026-02-17T08:26:06Z","publication_status":"published","type":"conference","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2025-07-08","location":"Aarhus, Denmark","end_date":"2025-07-11"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"mla":"Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20, doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>.","ista":"Goranci G, Henzinger M, Räcke H, Sricharan A. 2025. Incremental approximate maximum flow via residual graph sparsification. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 334, 91:1-91:20.","apa":"Goranci, G., Henzinger, M., Räcke, H., &#38; Sricharan, A. (2025). Incremental approximate maximum flow via residual graph sparsification. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334, p. 91:1-91:20). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, 334:91:1-91:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>.","ieee":"G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334, p. 91:1-91:20.","ama":"Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum flow via residual graph sparsification. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:91:1-91:20. doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>","short":"G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20."},"file_date_updated":"2026-02-18T09:02:33Z","author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Harald","full_name":"Räcke, Harald","last_name":"Räcke"},{"last_name":"Sricharan","first_name":"A.","full_name":"Sricharan, A."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"arxiv":1,"page":"91:1-91:20","publication_identifier":{"isbn":["9783959773720"]},"volume":334,"acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI\r\n10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Harald Räcke: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858 and 470029389.","file":[{"file_size":944824,"date_updated":"2026-02-18T09:02:33Z","file_name":"2025_ICALP_Goranci.pdf","creator":"dernst","file_id":"21315","success":1,"checksum":"c178cf554e44204b9f64ebd9b54cf7ba","relation":"main_file","access_level":"open_access","date_created":"2026-02-18T09:02:33Z","content_type":"application/pdf"}]},{"external_id":{"arxiv":["2407.11752"]},"alternative_title":["LIPIcs"],"department":[{"_id":"KrCh"}],"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"oa_version":"Published Version","ec_funded":1,"_id":"21320","abstract":[{"lang":"eng","text":"Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. \r\nThis model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the  ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms."}],"status":"public","month":"06","day":"30","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"IID prophet inequality with random horizon: Going beyond increasing hazard rates","OA_type":"gold","OA_place":"publisher","has_accepted_license":"1","year":"2025","date_created":"2026-02-18T10:44:14Z","publication_status":"published","doi":"10.4230/LIPIcs.ICALP.2025.87","fulldoi":"https://doi.org/10.4230/LIPIcs.ICALP.2025.87","article_processing_charge":"No","publication":"52nd International Colloquium on Automata, Languages, and Programming","date_published":"2025-06-30T00:00:00Z","intvolume":"       334","quality_controlled":"1","date_updated":"2026-09-16T07:25:05Z","conference":{"end_date":"2025-07-11","start_date":"2025-07-08","name":"ICALP: Automata, Languages and Programming","location":"Aarhus, Denmark"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"chicago":"Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>.","ista":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. 2025. IID prophet inequality with random horizon: Going beyond increasing hazard rates. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 334.","mla":"Giambartolomei, Giordano, et al. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>.","apa":"Giambartolomei, G., Mallmann-Trenn, F., &#38; Saona Urmeneta, R. J. (2025). IID prophet inequality with random horizon: Going beyond increasing hazard rates. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>","short":"G. Giambartolomei, F. Mallmann-Trenn, R.J. Saona Urmeneta, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality with random horizon: Going beyond increasing hazard rates. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>","ieee":"G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet inequality with random horizon: Going beyond increasing hazard rates,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334."},"file_date_updated":"2026-02-19T07:41:55Z","author":[{"first_name":"Giordano","full_name":"Giambartolomei, Giordano","last_name":"Giambartolomei"},{"last_name":"Mallmann-Trenn","full_name":"Mallmann-Trenn, Frederik","first_name":"Frederik"},{"first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta"}],"type":"conference","acknowledgement":"We would like to thank José Correa for his precious advice, Bruno Ziliotto and Vasilis Livanos for early conversations. Giambartolomei, Giordano: EPSRC grants EP/W005573/1 and EP/X021696/1. Mallmann-Trenn, Frederik: EPSRC grant EP/W005573/1. Saona, Raimundo: ERC grant CoG 863818 (ForM-SMArt), ANID Chile grant ACT210005, French Agence Nationale de la Recherche (ANR) grant ANR-21-CE40-0020 (CONVERGENCE), and Austrian Science Fund (FWF) grant 10.55776/COE12.","file":[{"success":1,"file_id":"21331","creator":"dernst","file_name":"2025_ICALP_Giambartolomei.pdf","date_updated":"2026-02-19T07:41:55Z","file_size":876167,"content_type":"application/pdf","date_created":"2026-02-19T07:41:55Z","access_level":"open_access","relation":"main_file","checksum":"960110956c26a5cefadde8e47888bfbe"}],"publication_identifier":{"isbn":["9783959773720"]},"volume":334,"oa":1,"language":[{"iso":"eng"}],"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"]},{"year":"2025","publication_status":"published","date_created":"2026-02-17T07:49:17Z","fulldoi":"https://doi.org/10.4230/LIPIcs.ICALP.2025.150","doi":"10.4230/LIPIcs.ICALP.2025.150","article_processing_charge":"No","scopus_import":"1","publication":"52nd International Colloquium on Automata, Languages, and Programming","date_published":"2025-07-30T00:00:00Z","quality_controlled":"1","date_updated":"2026-09-16T07:23:50Z","external_id":{"arxiv":["2504.15960"]},"alternative_title":["LIPIcs"],"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"department":[{"_id":"KrCh"}],"_id":"21268","abstract":[{"lang":"eng","text":"We consider multiple-environment Markov decision processes (MEMDP), which consist of a finite set of MDPs over the same state space, representing different scenarios of transition structure and probability. The value of a strategy is the probability to satisfy the objective, here a parity objective, in the worst-case scenario, and the value of an MEMDP is the supremum of the values achievable by a strategy.\r\nWe show that deciding whether the value is 1 is a PSPACE-complete problem, and even in P when the number of environments is fixed, along with new insights to the almost-sure winning problem, which is to decide if there exists a strategy with value 1. Pure strategies are sufficient for theses problems, whereas randomization is necessary in general when the value is smaller than 1. We present an algorithm to approximate the value, running in double exponential space. Our results are in contrast to the related model of partially-observable MDPs where all these problems are known to be undecidable."}],"ec_funded":1,"oa_version":"Published Version","month":"07","day":"30","status":"public","corr_author":"1","title":"The value problem for multiple-environment MDPs with parity objective","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","OA_type":"gold","OA_place":"publisher","acknowledgement":"Krishnendu Chatterjee: ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund\r\n(FWF) 10.55776/COE12. Jean-François Raskin: PDR Weave project FORM-LEARN-POMDP funded by FNRS and DFG, and the support of the Fondation ULB. Ocan Sankur: ANR BisoUS (ANR-22-CE48-0012) and ANR EpiRL (ANR-22-CE23-0029).","file":[{"content_type":"application/pdf","date_created":"2026-02-18T07:50:56Z","access_level":"open_access","relation":"main_file","checksum":"4477a7fd4fbf0ba6c8e9b15683b5a6b8","success":1,"file_id":"21313","creator":"dernst","date_updated":"2026-02-18T07:50:56Z","file_name":"2025_LIPIcs_Chatterjee.pdf","file_size":1075724}],"publication_identifier":{"isbn":["9783959773720"]},"arxiv":1,"language":[{"iso":"eng"}],"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Jean-Francois Raskin, and Ocan Sankur. “The Value Problem for Multiple-Environment MDPs with Parity Objective.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">https://doi.org/10.4230/LIPIcs.ICALP.2025.150</a>.","mla":"Chatterjee, Krishnendu, et al. “The Value Problem for Multiple-Environment MDPs with Parity Objective.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, 150, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">10.4230/LIPIcs.ICALP.2025.150</a>.","ista":"Chatterjee K, Doyen L, Raskin J-F, Sankur O. 2025. The value problem for multiple-environment MDPs with parity objective. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, , 150.","apa":"Chatterjee, K., Doyen, L., Raskin, J.-F., &#38; Sankur, O. (2025). The value problem for multiple-environment MDPs with parity objective. In <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">https://doi.org/10.4230/LIPIcs.ICALP.2025.150</a>","short":"K. Chatterjee, L. Doyen, J.-F. Raskin, O. Sankur, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"Chatterjee K, Doyen L, Raskin J-F, Sankur O. The value problem for multiple-environment MDPs with parity objective. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.150\">10.4230/LIPIcs.ICALP.2025.150</a>","ieee":"K. Chatterjee, L. Doyen, J.-F. Raskin, and O. Sankur, “The value problem for multiple-environment MDPs with parity objective,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"conference":{"end_date":"2025-07-11","name":"ICALP: Automata, Languages and Programming","start_date":"2025-07-08","location":"Aarhus, Denmark"},"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"},{"last_name":"Raskin","full_name":"Raskin, Jean-Francois","first_name":"Jean-Francois"},{"last_name":"Sankur","first_name":"Ocan","full_name":"Sankur, Ocan"}],"file_date_updated":"2026-02-18T07:50:56Z","type":"conference","article_number":"150"}]