[算法理论] 贪婪补全：加权 $(\eta,\eta)$-间隔的突破

摘要

我们研究加权图的 $(\eta,\eta)$-间隔。本文提出了一种简单的贪婪补全程序，从稀疏的初始图出发，反复修正具有较差拉伸的顶点对，这一方法是对 Knudsen 的加法补全的推广。作为应用，我们构造了大小为 $\tilde{O}(n^{1+1/k})$ 的 $(k,k-1)$-间隔，这在之前是未知的。

关键技术细节

贪婪补全算法的核心在于：

1. 稀疏初始图：从一个稀疏图开始，确保初始步骤的高效性。
2. 顶点对修正：通过修正拉伸较差的顶点对来不断提升图的质量。
3. 拉伸概念：在加权图中，拉伸定义为顶点对之间的最短路径长度与其在原图中距离的比率。

算法实现

下面是伪代码示例，展示了贪婪补全的基本过程：

function greedyCompletion(graph):
    while exists bad stretch pair (u, v) in graph:
        fixPair(u, v)
    return graph

该算法通过不断修正图中顶点对的拉伸，逐步得到更优的 $(\eta,\eta)$-间隔。

博主点评： 本文展示了贪婪算法在图论中的有效应用，尤其是在加权图的补全问题上。通过简单的贪婪策略，作者成功构建了新的 $(k,k-1)$-间隔，为后续研究提供了重要基础。