Approximation Algorithms for Directed Weighted Spanners

Grigorescu, Elena

doi:10.1007/s00453-026-01384-6

2026-04-13

Grigorescu, Elena *

Kumar, Nithish

Lin, Young-San

DOI：10.1007/s00453-026-01384-6

原文链接

原文求助

摘要

En 中文

在成对加权Spanner问题中，我们给定一个具有n个顶点和k个终端顶点对的 directed graph。每条边被赋予成本和长度。目标是找到一个满足终端距离约束的最小成本子图。Elkin和Peleg（Theory of Computing Systems, 2007）在一个标准复杂性假设下证明，该问题的更受限变体在近似上具有O(2(log1-epsilon n))-hard性。这种一般化表述涵盖了包括Spanner、距离保持器和Steiner森林在内的许多经过充分研究的网络连通性问题描述。对于加权Spanner问题，其中边的长度为正整数且大小为n的多项式，我们展示了一个O(n(4/5+epsilon))-近似算法。当边的成本和长度为单位值时，最佳先前算法由Chlamtáč、Dinitz、Kortsarz和Laekhanukit（Transactions on Algorithms, 2020）给出，提供O(n(3/5+epsilon))-近似比。我们还考虑了在线设置，其中顶点对逐个到达，且必须不可撤销地添加边以满足距离约束。我们展示了一个O(n(1/2+epsilon))-竞争比算法。当前最佳结果包括：当边的成本为单位值且长度为任意正值时，Grigorescu、Lin和Quanrud（APPROX, 2021）提出的O(n(4/5))-竞争比算法；当边的成本和长度为单位值时，提出的min{O(n(1/2+epsilon)),O(n(2/3+epsilon))}-竞争比算法。据我们所知，我们的结果是加权Spanner问题中具有次线性近似（竞争）比的首个近似（在线）多项式时间算法。

Keyword:

Directed spanners

Directed steiner forests

Approximation algorithms

Online algorithms