编辑推荐：
本文将经典生存网络设计问题（SNDP）推广至子集对连接需求场景，提出首个非平凡近似算法。同时揭示当连接需求较大时，基于路径数要求的近似算法存在Ω(q/log q)-hardness，补充了现有不可近似性结果。
为了查看此由人工智能生成的摘要，您必须拥有高级访问权限。
了解更多
登录
摘要
摘要
在经典的生存网络设计问题（SNDP）中，我们给定一个无向图 G = (V, E)，图中边带有成本，并且每对顶点之间存在连通性要求 k(s, t)。目标是找到一个最小成本的子图 H?G，使得每对顶点 (s, t) 都可以通过 k(s, t) 条边或（开放式的）顶点不相交的路径连接起来，分别称为 EC-SNDP 和 VC-SNDP。Jain 在 [FOCS’98, Combinatorica’01] 中提出了一个 EC-SNDP 的 2-近似算法；十年后，Chuzhoy 和 Khanna 在 [FOCS’09, Theory Comput.’12] 中发现了一个 VC-SNDP 的 O(k3log?n)-近似算法，其中 k 是最大的连通性要求。尽管关于 SNDP 的点对点设置有大量文献，但子集之间的连通性这一实际问题仍然了解较少。
本文关注将 EC-SNDP 推广到子集对子集设置的情况，即 Group EC-SNDP。我们开发了一个框架，为 Group EC-SNDP 提出了第一个非平凡的（真正的）近似算法。此前，只有针对 Group EC-SNDP 的双标准近似算法 [Chalermsook, Grandoni, 和 Laekhanukit, SODA’15]，以及仅针对单源变体且连通性要求为 k(S, T) ∈ {0, 1, 2} 的真正近似算法 [Gupta, Krishnaswamy, 和 Ravi, SODA’10; Khandekar, Kortsarz, 和 Nutov, FSTTCS’09 以及 Theor. Comput. Sci.’12]。
从负面角度来看，关于连通性需求的数量 q，我们得出了一个对于较大 k 值的 Ω(q/log?q)-难度结果，这补充了之前的不可近似性结论。例如，基于 k 的难度结果包括：k1/5 ? ε-难度 [Cheriyan 等人, SODA’12; Laekhanukit, SODA’14; Chalermsook 等人, SODA’15; Manurangsi, IPL’19]；基于 n 的难度结果包括：\(2^{\log ^{1-\varepsilon }n}\)-难度 [Chalermsook 等人, SODA’15]。
人工智能摘要
人工智能生成的摘要（实验性)
此摘要是通过自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现研究的价值、评估文章的相关性，并协助来自相关研究领域的读者理解文章内容。它旨在补充作者提供的摘要，后者仍然是文章的权威版本。点击此处了解更多。
点击 此处 对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的版本。
