SIMPLEX PARTITIONING VIA EXPONENTIAL CLOCKS AND THE MULTIWAY-CUT PROBLEM

摘要

The Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special 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 a solution to the geometric relaxation is equivalent to partitioning the simplex. We present a novel simplex partitioning algorithm which is based on two ingredients: competing exponential clocks and distortion. Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the multiway cut problem, we obtain a simple (4/3)-approximation algorithm, thus, improving upon the current best-known result. This bound is further pushed to obtain an approximation factor of 1.32388. It is known that under the assumption of the unique games conjecture, the best possible approximation for the Multiway-Cut problem can be attained via the geometric relaxation.