摘要
我们解决了Anari, Charikar和Ramakrishnan提出的薄匹配问题，达到多对数因子的效果。给定一个分数完美匹配 $x$，我们称完美匹配 $M$ 相对于 $x$ 是 $\eta$-薄的，如果对于任何切割 $(S,\bar{S})$，都有 $$ |M \cap E(S,\bar{S})| \leq \eta \cdot x(S,\bar{S}). $$
[ACR23] 推测，对于任何分数完美匹配 $x$，都存在一个完美匹配 $M$，使得其相对于 $x$ 是 $O(1)$-薄的。首先，我们展示如果 $M$ 被限制在 $x$ 的支持集内，则 $\eta \geq \Omega(n)$。我们通过设计一个高效算法，输出一个 $O(n \log n)$-薄的完美匹配，其中 $n$ 是顶点的数量。
随后，我们放宽这个约束，证明对于任何分数完美匹配 $x$，存在一个完美匹配 $M$（不必在 $x$ 的支持集内），使得 $M$ 是 $\text{polylog}(n)$-薄的。所有结果适用于双分图和非双分图。我们还讨论了这些结果在度量失真问题中的应用。
博主点评： 本文通过高效算法展示了薄完美匹配的强大应用潜力，尤其是在图论及其相关领域的研究中。多对数因子的引入不仅提升了算法的性能，也为解决实际问题提供了新的思路，值得进一步探索与应用。