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

The Taub Faculty of Computer Science Events and Talks

Approximating Requirement Cut via a Configuration LP
event speaker icon
Yotam Sharoni (M.Sc. Thesis Seminar)
event date icon
Sunday, 07.02.2021, 17:00
event location icon
Zoom Lecture: 98726136846
For password to lecture, please contact: yotamsh@cs.technion.ac.il
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.