M.Sc Thesis | |

M.Sc Student | Sharoni Yotam |
---|---|

Subject | Approximation Algorithm for Requirement Cut |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Roy Schwartz |

We consider the Requirement Cut problem, where given an undirected graph equipped with non-negative edge
weights , and groups of vertices each equipped with a requirement
, the goal is to find a
collection of edges , with total minimum weight, such
that once is removed from in the resulting graph every is broken into at least connected components.
Requirement Cut captures multiple classic cut problems in graphs, *e.g.*, Multicut, Multiway Cut, Min *k*-Cut, Steiner *k*-Cut,
Steiner Multicut, and Multi-Multiway Cut.
Nagarajan and Ravi [Algoritmica‘10] presented an approximation of for the problem, which was
subsequently improved to by Gupta, Nagarajan and Ravi
[Operations Research Letters‘10] (here and ). They also proved that there is
a hardness of approximation of when the graph is a tree. Thus,
providing a tight approximation when the graph is a tree. In both these works,
the main approach to solving (RC) in general graphs is first to formulate a
linear programming relaxation which finds a suitable spreading metric over the
vertices of , then transform the metric into
a tree metric, and finally round the solution on the tree. In the second work,
an additional greedy combinatorial approach is presented. In this approach the
algorithm repeatedly finds cuts that (approximately) minimize the ratio between
their cost and the number of groups they separate. This algorithm also yields
an approximation of for (RC).

We present an approximation of for Requirement Cut (here ). Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.