Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Approximating Requirement Cut via a Configuration LP
event speaker icon
Yotam Sharoni, M.Sc. Thesis Seminar
event date icon
Sunday, 7.2.2021, 17:00
event location icon
Zoom Lecture: 98726136846
For password to lecture, please contact:
event speaker icon
Advisor:  Dr. Roy Schwartz
We consider the REQUIREMENT CUT problem, where given an undirected graph G = (V, E) equipped with non-negative edge weights c , and g groups of vertices X1, . , Xg in V each equipped with a requirement ri, the goal is to find a collection of edges F in E, with total minimum weight, such that once F is removed from G in the resulting graph every Xi is broken into at least ri 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. We present an approximation for the problem, our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.
[Back to the index of events]