17 citations · 56 across the 22 of their papers we have counts for
8 papers · 1 filter
An SDP Primal-Dual Approximation Algorithm for Directed Hypergraph Expansion and Sparsest Cut with Product Demands
T-H. Hubert Chan, Bintao Sun
We give approximation algorithms for the edge expansion and sparsest cut with product demands problems on directed hypergraphs, which subsume previous graph models such as undirect…
Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators
T-H. Hubert Chan, Zhibin Liang
In a recent breakthrough STOC~2015 paper, a continuous diffusion process was considered on hypergraphs (which has been refined in a recent JACM 2018 paper) to define a Laplacian op…
Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian
T-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu +1
In spectral graph theory, the Cheeger's inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operat…
Online Submodular Maximization Problem with Vector Packing Constraint
T-H. Hubert Chan, Shaofeng H. -C. Jiang, Zhihao Gavin Tang +1
We consider the online vector packing problem in which we have a dimensional knapsack and items with weight vectors arrive online in an ar…
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…
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…
Spectral Properties of Laplacian and Stochastic Diffusion Process for Edge Expansion in Hypergraphs
T-H. Hubert Chan, Zhihao Gavin Tang, Chenzi Zhang
There has been recent work [Louis STOC 2015] to analyze the spectral properties of hypergraphs with respect to edge expansion. In particular, a diffusion process is defined on a hy…