17 citations · 56 across the 22 of their papers we have counts for
4 papers · 1 filter
On (, )-Restricted Max-Min Fair Allocation Problem
T-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu
We study the max-min fair allocation problem in which a set of indivisible items are to be distributed among agents such that the minimum utility among all agents is maximi…
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
T-H. Hubert Chan, Zhiyi Huang, Shaofeng H. -C. Jiang +2
We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm main…
A PTAS for the Steiner Forest Problem in Doubling Metrics
T-H. Hubert Chan, Shuguang Hu, Shaofeng H. -C. Jiang
We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean pl…
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
T-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang +1
The celebrated Cheeger's Inequality establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on…