<p>The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.</p>
<p>It seems like these problems would fall under the framework of network design problems (approximately) solvable with the primal-dual method.</p>
<p>However, I cannot find anything in the literature using these methods. Is a primal-dual approximation algorithm known for TAP or CacAP? Would it be interesting to find one, even if it does not improve upon the current best approximation ratios?</p>
<p>Thanks</p>

CC BY-SA 4.0
2021-10-21T13:52:18.060Z
The paper [Improved approximation for tree augmentation: saving by rewiring](https://scholar.google.com/scholar?cluster=43269301234901567&hl=en&as_sdt=0,22) says that the primal-dual algorithm in [Improved approximation algorithms for network design problems](https://scholar.google.com/scholar?cluster=10870724225515643310&hl=en&as_sdt=0,22) gives a 2-approximation for weighted Tree Augmentation.
Neal Young
CC BY-SA 4.0
2021-10-21T17:19:30.930Z
They are both special cases of Steiner connectivity augmentation problems for which a 2-approximation is known for a long time via primal-dual. See the survey of Goemans and Williamson. https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf
Chandra Chekuri
<reference-request><graph-theory><graph-algorithms><approximation-algorithms><optimization>
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
Karagounis Z
# Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

(Asked by: username_0 on 2021-10-21)

The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.

It seems like these problems would fall under the framework of network design problems (approximately) solvable with the primal-dual method.

However, I cannot find anything in the literature using these methods. Is a primal-dual approximation algorithm known for TAP or CacAP? Would it be interesting to find one, even if it does not improve upon the current best approximation ratios?

Thanks

**Tags:** reference-request, graph-theory, graph-algorithms, approximation-algorithms, optimization

> **Comments:**
> **username_1**: The paper [Improved approximation for tree augmentation: saving by rewiring](https://scholar.google.com/scholar?cluster=43269301234901567&hl=en&as_sdt=0,22) says that the primal-dual algorithm in [Improved approximation algorithms for network design problems](https://scholar.google.com/scholar?cluster=10870724225515643310&hl=en&as_sdt=0,22) gives a 2-approximation for weighted Tree Augmentation.  
> **username_2**: They are both special cases of Steiner connectivity augmentation problems for which a 2-approximation is known for a long time via primal-dual. See the survey of Goemans and Williamson. https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf  

---

## 0 answers

