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

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.