We study the robust maximum flow problem and the robust maximum flow over time problem where a given number of arcs $\Gamma$ may fail or may be delayed. Two prominent models have been introduced for these problems: either one assigns flow to arcs fulfilling weak flow conservation in any scenario, or one assigns flow to paths where an arc failure or delay affects a whole path. We provide a unifying framework by presenting novel general models, in which we assign flow to subpaths. These models contain the known models as special cases and unify their advantages in order to obtain less conservative robust solutions. We give a thorough analysis with respect to complexity of the general models. In particular, we show that the general models are essentially NP-hard, whereas, e.g. in the static case with $\Gamma = 1$ an optimal solution can be computed in polynomial time. Further, we answer the open question about the complexity of the dynamic path model for $\Gamma = 1$. We also compare the solution quality of the different models. In detail, we show that the general models have better robust optimal values than the known models and we prove bounds on these gaps.

翻译：我们研究强力最大流量问题和强力最大流量问题,在一定数量的弧值可能失败或可能推迟的情况下,在一定数量的损耗或可能推迟的情况下,我们研究强力最大流量问题和强力最大流量问题。我们为这些问题采用了两种突出的模式:要么将流量分配到在任何假设情况下都达到弱力流量保护的弧值,要么将流量流向到弧值失败或延迟影响整个路径的路径;我们通过提出我们将流量分配到子路径的新通用模型提供一个统一框架。这些模型包含已知的模型,作为特殊案例,并统一其优势,以便获得保守程度较低的稳健解决方案。我们对一般模型的复杂性进行了透彻的分析。特别是,我们表明,一般模型基本上是NP-硬的,而在静态情况下,如$\伽玛=1美元,一个最佳解决方案可以在多元时间中计算。此外,我们回答关于美元\伽玛=1美元的动态路径模型的复杂性的公开问题。我们还比较了不同模型的解决方案的质量。我们详细表明,一般模型比已知模型更坚固的最佳值,我们证明这些差距是约束的。