Robust flow model gap conjecture

Consider an instance of the robust flow models with uncertainty parameter ΓN\Gamma\in\mathbb{N}. Let fgmf^*_{\textit{gm}}, famf^*_{\textit{am}}, and fpmf^*_{\textit{pm}} denote the optimal values of the general, arc, and path models, respectively.

Robust flow gap conjecture. For any ΓN\Gamma\in\mathbb{N}, the inequalities

fgm(Γ+1)fpmf^*_{\textit{gm}}\leq (\Gamma+1)f^*_{\textit{pm}}

and

fam(Γ+1)fpmf^*_{\textit{am}}\leq (\Gamma+1)f^*_{\textit{pm}}

hold on every instance.

These inequalities conjecturally give tight upper bounds on how much the robust general and arc models can outperform the robust path model. The conjecture is motivated by examples and by tightness on directed acyclic graphs with Γ=1\Gamma=1; no general resolution is supplied.

Sources & referencesView supporting material

Primary source

Christian Biefel, Martina Kuchlbauer, Frauke Liers and Lisa Waldmüller, “Robust static and dynamic maximum flows”, arXiv:2202.10880 (2022).

Additional references

2 papers in this index state this conjecture (2011–2022). The statement above is taken from the most recent of them; the others are arXiv:1101.2915.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.