Lune

STOC2026Top-tier venue

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

Abstract

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and k designated terminals. The goal is to partition the vertices of the graph into k parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for k ≥ 3. The currently best known approximation algorithm for the problem for arbitrary k, obtained by Sharma and Vondrák [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of k ≥ 4 we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For k = 3 an optimal approximation algorithm is known.)

Our main technical contributions are new insights on rounding the LP relaxation of Cȃlinescu, Karloff, and Rabani [STOC 1998], whose integrality ratio matches Multiway Cut's approximability ratio, assuming the Unique Games Conjecture [Manokaran, Naor, Raghavendra, and Schwartz, STOC 2008]. First, we introduce a generalized form of a rounding scheme suggested by Kleinberg and Tardos [FOCS 1999] and use it to replace the Exponential Clocks rounding scheme used by Buchbinder, Naor, and Schwartz [STOC 2013] and by Sharma and Vondrák. Second, while previous algorithms use a mixture of two, three, or four basic rounding schemes, each from a different family of rounding schemes, our algorithm uses a computationally-discovered mixture of hundreds of basic rounding schemes, each parametrized by a random variable with a distinct probability distribution, including in particular many different rounding schemes from the same family. We give a completely rigorous analysis of our improved algorithms using a combination of analytical techniques and interval arithmetic.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. Tight approximability of MAX 2-SAT and relatives, under UGCJoshua Brakensiek, Neng Huang, Uri ZwickSODA 2024 · 3 citations
  2. Separating MAX 2-AND, MAX DI-CUT and MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickFOCS 2023 · 3 citations
  3. Representative set statements for delta-matroids and the Mader delta-matroidMagnus WahlströmSODA 2024 · 2 citations

Related papers

  1. A Parameterized Approximation Scheme for Min kk-CutDaniel Lokshtanov, Saket Saurabh, Vaishali SurianarayananFOCS 2020 · 22 citations
  2. The metric relaxation for 0-extension admits an Ω(log2/3k) gapRoy Schwartz, Nitzan TurSTOC 2021
  3. Planar Multiway Cut with Terminals on Few FacesSukanya Pandey, Erik Jan van LeeuwenSODA 2022 · 1 citation
  4. A nearly 5/3-approximation FPT Algorithm for Min-k-CutKen-ichi Kawarabayashi, Bingkai LinSODA 2020 · 11 citations
  5. A quasipolynomial (2 + ε)-approximation for planar sparsest cutVincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason LiSTOC 2021 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines