1 citations · 1 across the 2 of their papers we have counts for
6 papers
Online Matching on -Uniform Hypergraphs
Sander Borst, Danish Kashaev, Zhuan Khye Koh
The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio…
On Circuit Diameter and Straight Line Complexity
Daniel Dadush, Stefan Kober, Zhuan Khye Koh
The circuit diameter of a polyhedron is the maximum length (number of steps) of a shortest circuit walk between any two vertices of the polyhedron. Introduced by Borgwardt, Finhold…
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
We present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph on edges…
Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
Zhuan Khye Koh, Georg Loho
Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches…
On the Correlation Gap of Matroids
Edin HusiÄ, Zhuan Khye Koh, Georg Loho +1
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the per…
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015) as a relaxation of the combinatorial diameter. We show that the circuit diam…