@inproceedings{21280,
  abstract     = {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.},
  author       = {Goranci, Gramoz and Henzinger, Monika H and Räcke, Harald and Sricharan, A.},
  booktitle    = {52nd International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959773720},
  location     = {Aarhus, Denmark},
  pages        = {91:1--91:20},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Incremental approximate maximum flow via residual graph sparsification}},
  doi          = {10.4230/lipics.icalp.2025.91},
  volume       = {334},
  year         = {2025},
}

@inproceedings{21320,
  abstract     = {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. 
This 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.},
  author       = {Giambartolomei, Giordano and Mallmann-Trenn, Frederik and Saona Urmeneta, Raimundo J},
  booktitle    = {52nd International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959773720},
  location     = {Aarhus, Denmark},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{IID prophet inequality with random horizon: Going beyond increasing hazard rates}},
  doi          = {10.4230/LIPIcs.ICALP.2025.87},
  volume       = {334},
  year         = {2025},
}

@inproceedings{21268,
  abstract     = {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.
We 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.},
  author       = {Chatterjee, Krishnendu and Doyen, Laurent and Raskin, Jean-Francois and Sankur, Ocan},
  booktitle    = {52nd International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783959773720},
  location     = {Aarhus, Denmark},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{The value problem for multiple-environment MDPs with parity objective}},
  doi          = {10.4230/LIPIcs.ICALP.2025.150},
  year         = {2025},
}