Simplex Transformations and the Multiway Cut Problem

• 成果类型: Article
• 署名作者: Buchbinder, Niv; Schwartz, Roy; Weizman, Baruch
• 署名单位: Tel Aviv University; Technion Israel Institute of Technology; Tel Aviv University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1073
• 发表日期: 2021
• 页码: 757-771
• 关键词: approximation algorithms; THEOREMS; schemes; hard

摘要

We consider multiway cut, 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 to 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 a computer was partly used in verifying its approximation factor. 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 an approximation guarantee for the multiway cut problem that (roughly) matches the current best computer-verified approximation factor.