论文标题
在近乎最佳的时间和记忆中，低直径图的近似最低均值循环
Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
论文作者
论文摘要
我们重新审视Min-Mean-Cycle，这是在平均重量最小的加权定向图中找到周期的经典问题。尽管有广泛的算法文献，但以前的工作在边缘$ m $的数量中却没有接近线性的运行时间。我们提出了一种近似算法，该算法对于具有多组直径的图形，可以达到接近线性的运行时。特别是，这是第一个算法，其运行时在顶点$ n $中缩放为$ \ tilde {o}（n^2）$，用于完整图。此外，在直径上无条件地，该算法仅使用$ o（n）$内存，而不是阅读输入，使其“内存 - 最佳”。我们的方法是基于使用熵正则化解决线性编程松弛的基础，从而减少了矩阵平衡的问题 - 大量减少了最佳运输到矩阵缩放的最佳运输。该算法是实用且易于实现的。
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work falls short of a near-linear runtime in the number of edges $m$. We propose an approximation algorithm that, for graphs with polylogarithmic diameter, achieves a near-linear runtime. In particular, this is the first algorithm whose runtime scales in the number of vertices $n$ as $\tilde{O}(n^2)$ for the complete graph. Moreover, unconditionally on the diameter, the algorithm uses only $O(n)$ memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming relaxation using entropic regularization, which reduces the problem to Matrix Balancing -- á la the popular reduction of Optimal Transport to Matrix Scaling. The algorithm is practical and simple to implement.
