Warm-starting Push-Relabel

Push-Relabel 是最著名的网络流算法之一。它通过维护一个饱和割的预流，比其他流算法（如 Ford-Fulkerson 算法）具有更好的理论和实证运行时间。在实践中，Push-Relabel 的速度甚至比理论保证的速度更快，部分原因是使用了良好的启发式方法来种子和更新迭代算法。然而，如何在不一定是预流或饱和割的任意初始化上运行 Push-Relabel 仍然不清楚。我们提供了第一个关于使用预测流进行热启动 Push-Relabel 的理论保证，其中我们的学习增强版本在预测流接近最优流时具有快速的运行时间，同时保持强大的最坏情况保证。有趣的是，我们的算法使用了间隙重贴标号启发式方法，这种方法在实践中长期以来一直被使用，但在我们的工作之前，尚未有严格的理论证明说明它可以导致运行时间的改进。然后，我们提供实验结果，表明我们的热启动 Push-Relabel 在实践中也表现良好。

本论文旨在解决Push-Relabel算法在初始化不是预流或切割饱和的情况下的运行问题。论文提出了一种基于学习的算法，可以在预测流接近最优流时获得更快的运行时间，同时保持鲁棒的最坏情况保证。

本文提出的算法是一种基于学习的Push-Relabel算法，可以在预测流接近最优流时获得更快的运行时间，同时保持鲁棒的最坏情况保证。该算法使用了长期以来在实践中使用的间隙重标记启发式算法，但在此之前，尚未对其进行严格的理论证明。

本文提出的算法可以解决Push-Relabel算法在初始化不是预流或切割饱和的情况下的运行问题。该算法使用了基于学习的策略，可以在预测流接近最优流时获得更快的运行时间，同时保持鲁棒的最坏情况保证。实验结果表明，该算法在实践中也表现良好。

在这个领域中，最近的相关研究包括基于深度学习的网络流算法和其他启发式算法，如HLPP和Dinic算法。