1 citations · 2 across the 6 of their papers we have counts for
9 papers
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…
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 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…
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…
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceler…
An Efficient Characterization of Submodular Spanning Tree Games
Zhuan Khye Koh, Laura Sanità
Cooperative games are an important class of problems in game theory, where the goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitio…
Stabilizing Weighted Graphs
Zhuan Khye Koh, Laura Sanità
An edge-weighted graph is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an importan…