1 citations · 2 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…