Relaxed Multi-Commodity Flow and its Application to the Design of Approximation Algorithms

A common framework for designing approximation algorithms for
such problems is the primal-dual method. In many cases, however,
the integrality gap is large, and thus, it is not possible to
obtain small (constant) approximation factors via this approach.
We have developed a technique for overcoming this obstacle in
certain cases. Suppose that the dual problem is some form of the
multi-commodity flow problem. A new version of the flow problem
is defined which we call relaxed multi-commodity flow. The main
feature of this new flow function is that it distinguishes
between inter-commodity and intra-commodity constraints, and
relaxes the inter-commodity constraint. We apply this technique
to two problems: the directed multiway cut problem and the subset
feedback set problem. In both cases we obtain constant
approximation factors which improve upon logarithmic
approximation factors previously known.
The following polynomial time approximation algorithms were
obtained:
(1) An approximation algorithm that achieves a factor of 2 for
the minimum weight multiway cut problem in directed graphs.
(2) An approximation algorithm that achieves a factor of 2 for
the minimum weight subset feedback edge set problem.
(3) An approximation algorithm that achieves a factor of 8 for
the minimum weight subset feedback vertex set problem.


Joint work with J. Naor