Simplex Transformations and the Multiway Cut Problem

Niv Buchbinder (), Roy Schwartz () and Baruch Weizman ()
Additional contact information
Niv Buchbinder: Statistics and Operations Research Department, Tel Aviv University, Tel Aviv 6997801, Israel
Roy Schwartz: Computer Science Department, Technion, Haifa 3200003, Israel
Baruch Weizman: The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel

Mathematics of Operations Research, 2021, vol. 46, issue 2, 757-771

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

Keywords: Primary: 68W25; Primary: Analysis of algorithms; suboptimal algorithms; Secondary: mathematics; combinatorics; multiway cut; approximation algorithms; randomized rounding (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1073 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:2:p:757-771

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().