0
$\begingroup$

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

Improve this question
$\endgroup$
2

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.