Uri Zwick

collaborators

3 papers

cs.DS2026

Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs

Uri Zwick

We give a concise description and an improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based, possibly infinite duration, stochastic or non…

cs.DS2026

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

Joshua Brakensiek, Neng Huang, Aaron Potechin +1

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 grap…

cs.DS2025

Improved girth approximation in weighted undirected graphs

Avi Kadria, Liam Roditty, Aaron Sidford +2

Let $G = (V, E, ℓ)$ be a $n$ -node $m$ -edge weighted undirected graph, where $ℓ : E \to (0, \infty)$ is a real \emph{length} function defined on its edges, and let $g$ den…