We study an algorithmic problem in network design called \(\mathcal {F}\) -augmentation where a family of cuts \(\mathcal {F}\)  is given and the goal is to find a minimum-cost edge set that covers each cut in \(\mathcal {F}\) . When \(\mathcal {F}\) is a so-called uncrossable family, Williamson et al. (Combinatorica 1995) provided a 2-approximation algorithm based on the primal-dual method. Extending their results to families that are non-uncrossable has remained a challenging question. In this paper, we introduce the notion of the crossing density of a set family and present a new approach to analyzing primal-dual algorithms based on this notion. We focus on pliable families, a strict generalization of uncrossable families, and provide the first O(1)-approximation algorithm for \(\mathcal {F}\) -augmentation of pliable families. Pliable families were introduced by Bansal et al. (Algorithmica 2024). We also improve on the results in Bansal et al. (Algorithmica 2024) by providing a 6-approximation algorithm for the \(\mathcal {F}\) -augmentation problem when \(\mathcal {F}\) is a family of small cuts. Our improvement implies improved approximation algorithms for the Capacitated Network Design problem. Finally, we study the (p, 3)-flexible graph connectivity problem. By carefully analyzing the structure of feasible solutions and using the techniques developed in this paper, we provide the first O(1)-approximation algorithm for this problem, exhibiting a 12-approximation algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Global Analysis of the Primal-Dual Method for Edge Augmentation Problems

  • Ishan Bansal

摘要

We study an algorithmic problem in network design called \(\mathcal {F}\) -augmentation where a family of cuts \(\mathcal {F}\)  is given and the goal is to find a minimum-cost edge set that covers each cut in \(\mathcal {F}\) . When \(\mathcal {F}\) is a so-called uncrossable family, Williamson et al. (Combinatorica 1995) provided a 2-approximation algorithm based on the primal-dual method. Extending their results to families that are non-uncrossable has remained a challenging question. In this paper, we introduce the notion of the crossing density of a set family and present a new approach to analyzing primal-dual algorithms based on this notion. We focus on pliable families, a strict generalization of uncrossable families, and provide the first O(1)-approximation algorithm for \(\mathcal {F}\) -augmentation of pliable families. Pliable families were introduced by Bansal et al. (Algorithmica 2024). We also improve on the results in Bansal et al. (Algorithmica 2024) by providing a 6-approximation algorithm for the \(\mathcal {F}\) -augmentation problem when \(\mathcal {F}\) is a family of small cuts. Our improvement implies improved approximation algorithms for the Capacitated Network Design problem. Finally, we study the (p, 3)-flexible graph connectivity problem. By carefully analyzing the structure of feasible solutions and using the techniques developed in this paper, we provide the first O(1)-approximation algorithm for this problem, exhibiting a 12-approximation algorithm.