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

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Simplex Transformations and the Multiway Cut Problem
event speaker icon
Baruch Weizman (Tel Aviv University)
event date icon
Wednesday, 09.11.2016, 12:30
event location icon
Taub 201
We consider the Multiway Cut problem, a basic graph partitioning problem in which the goal is to find the minimum weight collection of edges disconnecting a given set of special vertices called terminals. Multiway Cut admits a well known simplex embedding relaxation, where rounding this embedding is equivalent to partitioning the simplex. Current best known solutions for the problem are comprised of a mix of several different ingredients, resulting in intricate algorithms. Moreover, the best of these algorithms is too complex to fully analyze analytically and its approximation factor was verified using a computer. We propose a new approach to simplex partitioning and the Multiway Cut problem based on general transformations of the simplex that allow dependencies between the different variables. Our approach admits much simpler algorithms, and in addition yields a provable approximation guarantee for the Multiway Cut problem that: (1) improves upon the current best provable bound, and (2) (roughly) matches the computer verified best approximation factor.