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?



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.