NeFut Logo NeFut
EN 管理员登录

[算法理论] 成对重连用于成本-距离 Steiner 树

发布于:2026-11-09 22:00 最后更新:2026-11-12 00:51
#algorithm #Tree #Graph

Uniform 成本-距离 Steiner 树问题要求在给定根节点的情况下,构造一棵树,使得连边费用与根到终端的距离加权和之和最小。我们提出一种算法,同时构造两棵候选树:第一棵直接把所有终端连到根;第二棵先在选定的顶点之间做配对,再把每对通过一条边连回根。算法比较两棵树的目标值,取较小者。该随机化算法在生成树情形下的期望近似比为 $1.698$,在一般情形下为 $2.041$,且可以在多项式时间内去随机化。关键的配对匹配分析将部分增广费用直接归因于最优解的连通成本和延迟成本,而不是仅归因于以往分析使用的分离下界,从而使 $1.698$ 的因子低于最优值与该下界之间的最大乘法间隙 $1+1/\sqrt{2}$。我们给出实例族,使得从最小生成树出发的割-重连算法的近似比下界趋近于 $1+1/\sqrt{2}$,而本文算法的下界趋近于 $3/2$。最后证明 Uniform 成本-距离 Steiner 树问题与 Cable‑Trench 问题的 Steiner 树版本在近似意义上等价,误差可控制在任意小的加法损失。\n\n点评:该工作通过创新的配对策略显著提升了成本-距离 Steiner 树的近似性能,并提供了可去随机化的多项式算法,为相关网络设计问题提供了新的理论工具。

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

[h] 返回首页