Push-Relabel is one of the most celebrated network flow algorithms.
Maintaining a pre-flow that saturates a cut, it enjoys better theoretical and
empirical running time than other flow algorithms, such as Ford-Fulkerson. In
practice, Push-Relabel is even faster than what theoretical guarantees can
promise, in part because of the use of good heuristics for seeding and updating
the iterative algorithm. However, it remains unclear how to run Push-Relabel on
an arbitrary initialization that is not necessarily a pre-flow or
cut-saturating. We provide the first theoretical guarantees for warm-starting
Push-Relabel with a predicted flow, where our learning-augmented version
benefits from fast running time when the predicted flow is close to an optimal
flow, while maintaining robust worst-case guarantees. Interestingly, our
algorithm uses the gap relabeling heuristic, which has long been employed in
practice, even though prior to our work there was no rigorous theoretical
justification for why it can lead to run-time improvements. We then provide
experiments that show our warm-started Push-Relabel also works well in
practice.

Push-Relabel 是一种最受欢迎的网络流算法，我们提供了第一个理论保证来支持预测流进行 Push-Relabel 的热启动，并展示了在实践中该算法也表现良好。