8 citations · 20 across the 13 of their papers we have counts for
4 papers · 1 filter
Extensions of Self-Improving Sorters
Siu-Wing Cheng, Kai Jin, Lie Yan
Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to an unknown input distribution in a training phase. The input numbers …
Restricted Max-Min Allocation: Approximation and Integrality Gap
Siu-Wing Cheng, Yuchen Mao
Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most . However, their proof does not give…
Implicit Manifold Reconstruction
Siu-Wing Cheng, Man-Kwun Chiu
Let be a compact, smooth and boundaryless manifold with dimension and unit reach. We show how to construct a function $φ: \mathbb{R}^d \rightarr…
A note on self-improving sorting with hidden partitions
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin
We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(π(I)) + n), where I is the given input which contains n e…