---
OA_place: publisher
OA_type: gold
_id: '21280'
abstract:
- lang: eng
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.
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."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: A.
full_name: Sricharan, A.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum
flow via residual graph sparsification. In: 52nd International Colloquium on
Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2025:91:1-91:20. doi:10.4230/lipics.icalp.2025.91'
apa: 'Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. (2025). Incremental
approximate maximum flow via residual graph sparsification. In 52nd International
Colloquium on Automata, Languages, and Programming (Vol. 334, p. 91:1-91:20).
Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2025.91'
chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental
Approximate Maximum Flow via Residual Graph Sparsification.” In 52nd International
Colloquium on Automata, Languages, and Programming, 334:91:1-91:20. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/lipics.icalp.2025.91.
ieee: G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate
maximum flow via residual graph sparsification,” in 52nd International Colloquium
on Automata, Languages, and Programming, Aarhus, Denmark, 2025, vol. 334,
p. 91:1-91:20.
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.'
mla: Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual
Graph Sparsification.” 52nd International Colloquium on Automata, Languages,
and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025, p. 91:1-91:20, doi:10.4230/lipics.icalp.2025.91.
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.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
corr_author: '1'
date_created: 2026-02-17T08:26:06Z
date_published: 2025-06-30T00:00:00Z
date_updated: 2026-08-20T06:28:00Z
day: '30'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/lipics.icalp.2025.91
ec_funded: 1
external_id:
arxiv:
- '2502.09105'
file:
- access_level: open_access
checksum: c178cf554e44204b9f64ebd9b54cf7ba
content_type: application/pdf
creator: dernst
date_created: 2026-02-18T09:02:33Z
date_updated: 2026-02-18T09:02:33Z
file_id: '21315'
file_name: 2025_ICALP_Goranci.pdf
file_size: 944824
relation: main_file
success: 1
file_date_updated: 2026-02-18T09:02:33Z
fulldoi: https://doi.org/10.4230/lipics.icalp.2025.91
has_accepted_license: '1'
intvolume: ' 334'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 91:1-91:20
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22716'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Incremental approximate maximum flow via residual graph sparsification
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 334
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_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 \U0001D4A2 class in reliability theory. Moreover, we show that this does
not extend to its dual, the ̅\U0001D4A2 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."
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.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Giordano
full_name: Giambartolomei, Giordano
last_name: Giambartolomei
- first_name: Frederik
full_name: Mallmann-Trenn, Frederik
last_name: Mallmann-Trenn
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
citation:
ama: 'Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality
with random horizon: Going beyond increasing hazard rates. In: 52nd International
Colloquium on Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ICALP.2025.87'
apa: 'Giambartolomei, G., Mallmann-Trenn, F., & Saona Urmeneta, R. J. (2025).
IID prophet inequality with random horizon: Going beyond increasing hazard rates.
In 52nd International Colloquium on Automata, Languages, and Programming
(Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2025.87'
chicago: 'Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona
Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing
Hazard Rates.” In 52nd International Colloquium on Automata, Languages, and
Programming, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.87.'
ieee: 'G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet
inequality with random horizon: Going beyond increasing hazard rates,” in 52nd
International Colloquium on Automata, Languages, and Programming, Aarhus,
Denmark, 2025, vol. 334.'
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.” 52nd International Colloquium on Automata,
Languages, and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025, doi:10.4230/LIPIcs.ICALP.2025.87.'
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.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
date_created: 2026-02-18T10:44:14Z
date_published: 2025-06-30T00:00:00Z
date_updated: 2026-09-16T07:25:05Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2025.87
ec_funded: 1
external_id:
arxiv:
- '2407.11752'
file:
- access_level: open_access
checksum: 960110956c26a5cefadde8e47888bfbe
content_type: application/pdf
creator: dernst
date_created: 2026-02-19T07:41:55Z
date_updated: 2026-02-19T07:41:55Z
file_id: '21331'
file_name: 2025_ICALP_Giambartolomei.pdf
file_size: 876167
relation: main_file
success: 1
file_date_updated: 2026-02-19T07:41:55Z
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2025.87
has_accepted_license: '1'
intvolume: ' 334'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'IID prophet inequality with random horizon: Going beyond increasing hazard
rates'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 334
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_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."
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)."
alternative_title:
- LIPIcs
article_number: '150'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Jean-Francois
full_name: Raskin, Jean-Francois
last_name: Raskin
- first_name: Ocan
full_name: Sankur, Ocan
last_name: Sankur
citation:
ama: 'Chatterjee K, Doyen L, Raskin J-F, Sankur O. The value problem for multiple-environment
MDPs with parity objective. In: 52nd International Colloquium on Automata,
Languages, and Programming. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.ICALP.2025.150'
apa: 'Chatterjee, K., Doyen, L., Raskin, J.-F., & Sankur, O. (2025). The value
problem for multiple-environment MDPs with parity objective. In 52nd International
Colloquium on Automata, Languages, and Programming. Aarhus, Denmark: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2025.150'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Jean-Francois Raskin, and Ocan Sankur.
“The Value Problem for Multiple-Environment MDPs with Parity Objective.” In 52nd
International Colloquium on Automata, Languages, and Programming. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.150.
ieee: K. Chatterjee, L. Doyen, J.-F. Raskin, and O. Sankur, “The value problem for
multiple-environment MDPs with parity objective,” in 52nd International Colloquium
on Automata, Languages, and Programming, Aarhus, Denmark, 2025.
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.'
mla: Chatterjee, Krishnendu, et al. “The Value Problem for Multiple-Environment
MDPs with Parity Objective.” 52nd International Colloquium on Automata, Languages,
and Programming, 150, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025,
doi:10.4230/LIPIcs.ICALP.2025.150.
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.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
corr_author: '1'
date_created: 2026-02-17T07:49:17Z
date_published: 2025-07-30T00:00:00Z
date_updated: 2026-09-16T07:23:50Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2025.150
ec_funded: 1
external_id:
arxiv:
- '2504.15960'
file:
- access_level: open_access
checksum: 4477a7fd4fbf0ba6c8e9b15683b5a6b8
content_type: application/pdf
creator: dernst
date_created: 2026-02-18T07:50:56Z
date_updated: 2026-02-18T07:50:56Z
file_id: '21313'
file_name: 2025_LIPIcs_Chatterjee.pdf
file_size: 1075724
relation: main_file
success: 1
file_date_updated: 2026-02-18T07:50:56Z
fulldoi: https://doi.org/10.4230/LIPIcs.ICALP.2025.150
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The value problem for multiple-environment MDPs with parity objective
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...