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
Abstract:
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/