Robust flow model gap conjecture
Robust flow model gap conjecture
Consider an instance of the robust flow models with uncertainty parameter . Let , , and denote the optimal values of the general, arc, and path models, respectively.
Robust flow gap conjecture. For any , the inequalities
and
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 ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.