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