NeFut Logo NeFut
EN 管理员登录

[算法理论] 局部边际的力量:动态加权匹配的 $O(\varepsilon^{-1})$ 纵横比缩减

发布于:2026-08-31 22:00 最后更新:2026-09-02 01:49
#algorithm #Dynamic Programming #Graph

我们研究在边的插入与删除下的动态最大权匹配(MWM),关注两类目标:保持对最优权值的 $(1\pm\varepsilon)$ 近似,以及保持一个显式的 $(1-\varepsilon)$ 近似匹配。

本文的核心贡献是一个降维技巧:将任意多项式纵横比的实例转化为纵横比仅为 $O(\varepsilon^{-1})$ 的实例。该技巧对一般图均适用,且兼容部分动态(仅插入或仅删除)的更新模型。

降维的关键在于局部边际的结构性质。我们先把所有边按权值划分为若干权重类,然后观察某一类相对于所有更低类的全局边际贡献。该全局贡献可以用该类在一个局部窗口(窗口的纵横比为 $O(\varepsilon^{-1})$)内的边际贡献来近似。对所有窗口的局部边际求和得到值组合引理,该引理只需要每个局部窗口的近似最优值即可。

相较于 Gupta 与 Peng(FOCS 2013)的值降维,其局部纵横比为 $\varepsilon^{-\Theta(\varepsilon^{-1})}$,我们的方法将其提升到线性 $O(\varepsilon^{-1})$,显著削减了依赖。

同一结构性质还能用于显式匹配的组合,引入匹配组合引理。在 Bernstein 等人(SODA 2025)的框架中,局部纵横比原本是 $O(\varepsilon^{-2})$,我们将其改进为 $O(\varepsilon^{-1})$,从而在保持相同近似保证的前提下进一步提升效率。

点评:这篇工作通过对局部边际的细致分析,提供了一套统一且更紧凑的纵横比缩减工具。它不仅统一了值和匹配两类问题的降维思路,还在理论上显著改善了先前的指数依赖,为后续的动态加权匹配算法奠定了更坚实的基础。

原文链接: https://arxiv.org/abs/2608.27805

[h] 返回首页