Publications

(Unless stated otherwise, authors are sorted in alphabetical order.)

DBLP Google Scholar

2023

"Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang

SODA 2023

Bidder Subset Selection Problem in Auction Design

Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang

SODA 2023

2022

Prophet Matching with General Arrivals

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang

MOR 2022
Preliminary version appeared in EC 2020

Optimal Prophet Inequality with Less than One Sample

Nick Gravin, Hao Li, and Zhihao Gavin Tang

WINE 2022

Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design

Bo Peng, and Zhihao Gavin Tang

FOCS 2022

Lookahead Auctions with Pooling

Michal Feldman, Nick Gravin, Zhihao Gavin Tang, and Almog Wald

SAGT 2022

General Graphs are Easier than Bipartite Graphs: Tight Bounds for Secretary Matching

Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Gavin Tang

EC 2022

(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics

Zhihao Gavin Tang, Hongxun Wu and Jinzhao Wu

STOC 2022

Online Facility Location with Predictions

Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang and Yubo Zhang

ICLR 2022

Oblivious Online Contention Resolution Schemes

Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu and Qianfan Zhang

SOSA 2022

2021

Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang

COLT 2021

Online Selection Problems Against Constrained Adversary

Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang

ICML 2021

Random Order Vertex Arrival Contention Resolution Schemes For Matching, With Applications

Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang

ICALP 2021

Online Stochastic Matching with Edge Arrivals

Nick Gravin, Zhihao Gavin Tang, and Kangning Wang

ICALP 2021

2020

Tight Revenue Gaps among Simple Mechanisms

Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao

SICOMP 2020
Preliminary version appeared in SODA 2019

Fully Online Matching

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

JACM 2020
Preliminary version appeared in STOC 2018

Re-Revisiting Learning on Hypergraphs: Confidence Interval, Subgradient Method, and Extension to Multiclass

Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and T.-H. Hubert Chan (by contribution)

TKDE 2020
Preliminary version appeared in ICML 2017

Fully Online Matching II: Beating Ranking and Water-filling

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

FOCS 2020

Online Stochasitc Max-Weight Matching: prophet inequality for vertex and edge arrival models

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang

EC 2020

Towards a Better Understanding of Randomized Greedy Matching

Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

STOC 2020

2019

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

TALG 2019
Preliminary version appeared in ICALP 2018

Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian

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

TCS 2019

Tight Approximation Ratio of Anonymous Pricing

Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao

STOC 2019

Correlation-Robust Analysis of Single Item Auction

Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang

SODA 2019

Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model

Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang

SODA 2019

Tight Revenue Gaps among Simple Mechanisms

Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao

SODA 2019

2018

Spectral Properties of Hypergraph Laplacian and Approximation Algorithms

T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang

JACM 2018

Online Submodular Maximization with Free Disposal

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

TALG 2018
Preliminary version appeared in SODA 2017

On (1,ε)-Restricted Max-Min Fair Allocation Problem

T.-H. Hubert Chan, Zhihao Gavin Tang, and Xiaowei Wu

Algorithmica 2018 (Invited Paper)
Preliminary version appeared in ISAAC 2016

Online Makespan Minimization: The Power of Restart

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

APPROX 2018

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

ICALP 2018

How to Match when All Vertices Arrive Online

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu

STOC 2018

The Value of Information Concealment

Hu Fu, Christopher Liaw, Pinyan Lu, and Zhihao Gavin Tang

SODA 2018

2017

Online Submodular Maximization Problem with Vector Packing Constraint

T.-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, and Xiaowei Wu

ESA 2017

Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method

Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and T.-H. Hubert Chan (by contribution)

ICML 2017

Graph Edge Partitioning via Neighborhood Heuristic

Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, and Zhenguo Li (by contribution)

KDD 2017

Online Submodular Maximization with Free Disposal: Randomization Beats 1/4 for Partition Matroids

T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, and Zhihao Gavin Tang

SODA 2017

2016

On (1,ε)-Restricted Max-Min Fair Allocation Problem

T.-H. Hubert Chan, Zhihao Gavin Tang, and Xiaowei Wu

ISAAC 2016

2015

Cheeger Inequalities for General Edge-Weighted Directed Graphs

T.-H. Hubert Chan, Zhihao Gavin Tang, and Chenzi Zhang

COCOON 2015