Author name cluster

T.-H. Hubert Chan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2024 Journal Article

Max-min greedy matching problem: Hardness for the adversary and fractional variant

T.-H. Hubert Chan
Zhihao Gavin Tang
Quan Xue

Eden, Feige, and Feldman explored the concept of the max-min greedy matching problem, which can be conceived as a game played between an algorithm and an adversary. Both parties are presented with a bipartite graph consisting of items and players. Initially, the algorithm selects a priority order for the items, while the adversary, in turn, chooses a priority order for the players based on the algorithm's choice. These priority orders are then utilized in a greedy process to establish a matching between the items and players. During the process, when it is a player's turn, they select the highest priority item from their remaining available neighbors. The objective of the algorithm is to maximize the size of the resulting matching, while the adversary's goal is to minimize its size. Previous studies have demonstrated that the algorithm can employ a polynomial-time strategy to achieve a competitive ratio greater than 1 2. In this research, we present evidence that, from the adversary's standpoint, approximating the adversarial order minimum matching problem with a ratio better than 6 5 is NP-hard, assuming the small set expansion (SSE) hypothesis. Conversely, we introduce a fractional variant of the problem and analyze the interaction between the algorithm and the adversary when either or both parties are allowed to utilize fractional permutations. Notably, we discover that if the algorithm solely employs integral item permutations, then an optimal response from the adversary can also involve integral player permutations. Additionally, we establish that, in the fractional variant, the algorithm can adopt a round-robin strategy to achieve a competitive ratio of at least 1 − 1 / e for input graphs with a sufficiently large granularity parameter m. Furthermore, we demonstrate that the analysis for the round-robin strategy is tight even for regular graphs.

Details DOI

TCS Journal 2020 Journal Article

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 operator, whose spectral properties satisfy the celebrated Cheeger's inequality. However, one peculiar aspect of this diffusion process is that each hyperedge directs flow only from vertices with the maximum density to those with the minimum density, while ignoring vertices having strict in-between densities. In this work, we consider a generalized diffusion process, in which vertices in a hyperedge can act as mediators to receive flow from vertices with maximum density and deliver flow to those with minimum density. We show that the resulting Laplacian operator still has a second eigenvalue satisfying the Cheeger's inequality. Our generalized diffusion model shows that there is a family of operators whose spectral properties are related to hypergraph conductance, and provides a powerful tool to enhance the development of spectral hypergraph theory. Moreover, since every vertex can participate in the new diffusion model at every instant, this can potentially have wider practical applications.

Details DOI

TCS Journal 2019 Journal Article

Diffusion operator and spectral analysis for directed hypergraph Laplacian

T.-H. Hubert Chan
Zhihao Gavin Tang
Xiaowei Wu
Chenzi Zhang

In spectral graph theory, the Cheeger inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operator. Recently this inequality has been extended to undirected hypergraphs and directed normal graphs via a non-linear operator associated with a diffusion process in the underlying graph. In this work, we develop a unifying framework for defining a diffusion operator on a directed hypergraph with stationary vertices, which is general enough for the following two applications. 1. Cheeger's inequality for directed hyperedge expansion. 2. Quadratic optimization with stationary vertices in the context of semi-supervised learning. Despite the crucial role of the diffusion process in spectral analysis, previous works have not formally established the existence of the corresponding diffusion processes. In this work, we give a proof framework that can indeed show that such diffusion processes are well-defined. In the first application, we use the spectral properties of the diffusion operator to achieve the Cheeger's inequality for directed hyperedge expansion. In the second application, the diffusion operator can be interpreted as giving a continuous analog to the subgradient method, which moves the feasible solution in discrete steps towards an optimal solution.

Details DOI