DIMACS Theoretical Computer Science Seminar

Title: Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem

Speaker: Roy Schwartz, Princeton University

Date: Wednesday, April 8, 2015 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


Multiway Cut is a graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a special set of vertices called terminals. This problem is NP-hard and there is a well known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding the geometric relaxation is equivalent to partitioning the simplex. I will present a simplex partitioning method that is based on competing exponential clocks and distortion. Applying this method to Multiway Cut yields an extremely simple (4/3)-approximation, thus improving the previous best known algorithm of Karger et al. Further improvements by a follow-up work will also be discussed along with related open questions.

Joint work with Niv Buchbinder and Joseph (Seffi) Naor.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/