Our motivation is to improve on the best approximation guarantee known for the problem of finding a minimum-cost 2-node connected spanning subgraph of a given undirected graph with nonnegative edge costs. We present an LP (Linear Programming) relaxation based on partition constraints. The special case where the input contains a spanning tree of zero cost is called 2NC-TAP. We present a greedy algorithm for 2NC-TAP, and we analyze it via dual-fitting for our partition LP relaxation. Keywords: 2-node connected graphs, approximation algorithms, connectivity augmentation, greedy algorithm, network design, partition relaxation
翻译：我们的动机是改进已知的最佳近似保障,即找到一个以非负边缘成本连接的未定向图表的最小成本2节覆盖的子集的问题。我们展示了基于分区限制的LP(Lineear 编程程序)放松。输入含有一棵零成本覆盖的树的特例叫做2NC-TAP。我们为2NC-TAP提供了一种贪婪的算法,我们通过配方LP解密的双重配置来分析它。关键词:2-节点连接图表、近似算法、连接增强、贪婪算法、网络设计、分割放松。
相关内容
微信扫码咨询专知VIP会员