13 citations · 40 across the 21 of their papers we have counts for
25 papers
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…
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 designated terminals. The goal is to partition the vertices of the grap…
Improved girth approximation in weighted undirected graphs
Avi Kadria, Liam Roditty, Aaron Sidford +2
Let be a -node -edge weighted undirected graph, where is a real \emph{length} function defined on its edges, and let den…
Minimum-cost paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
An electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different c…
Optimal energetic paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +1
A weighted directed graph , where and , describes a road network in which an electric car can roam. An arc models a road segment co…
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…