17 citations · 95 across the 34 of their papers we have counts for
39 papers
Online Matching in Convex Bipartite Graphs
Yilong Feng, Zhihao Gavin Tang, Kangning Wang +1
Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where ea…
A Tight Bound on Online Vertex Cover under Edge Arrivals
Zhihao Gavin Tang, Yuhao Zhang
We prove a tight impossibility result for online vertex cover under edge arrivals. No randomized integral or fractional algorithm achieves a competitive ratio strictly below ag…
Fractional Fully Online Matching
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
This paper studies fractional matching on general graphs in the fully online model of Huang et al. (JACM 2020), in which all vertices arrive online and remain available for only a…
Prophet Secretary and Matching: the Significance of the Largest Item
Ziyun Chen, Zhiyi Huang, Dongchen Li +1
The prophet secretary problem is a combination of the prophet inequality and the secretary problem, where elements are drawn from known independent distributions and arrive in unif…
Incentives for Early Arrival in Cost Sharing
Junyu Zhang, Yao Zhang, Yaoxin Ge +4
In cooperative games, we study how values created or costs incurred by a coalition are shared among the members within it, and the players may join the coalition in a online manner…
Online Matching: A Brief Survey
Zhiyi Huang, Zhihao Gavin Tang, David Wajc
Matching, capturing allocation of items to unit-demand buyers, or tasks to workers, or pairs of collaborators, is a central problem in economics. Indeed, the growing prevalence of…
Sample-Based Matroid Prophet Inequalities
Hu Fu, Pinyan Lu, Zhihao Gavin Tang +3
We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, n…
Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
Tomer Ezra, Michal Feldman, Zhihao Gavin Tang
In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequenti…
Bidder Subset Selection Problem in Auction Design
Xiaohui Bei, Nick Gravin, Pinyan Lu +1
Motivated by practical concerns in the online advertising industry, we study a bidder subset selection problem in single-item auctions. In this problem, a large pool of candidate b…
On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching
Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu +2
Ranking and Balance are arguably the two most important algorithms in the online matching literature. They achieve the same optimal competitive ratio of for the integral ve…
Lookahead Auctions with Pooling
Almog Wald, Michal Feldman, Nick Gravin +1
A Lookahead Auction (LA), introduced by Ronen, is an auction format for the sale of a single item among multiple buyers, which is considered simpler and more fair than the optimal…
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochast…
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
Bo Peng, Zhihao Gavin Tang
In the classical prophet inequality, a gambler faces a sequence of items, whose values are drawn independently from known distributions. Upon the arrival of each item, its value is…
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin, Enze Sun, Zhihao Gavin Tang
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of go…
Improved Bounds for Fractional Online Matching Problems
Zhihao Gavin Tang, Yuhao Zhang
Online bipartite matching with one-sided arrival and its variants have been extensively studied since the seminal work of Karp, Vazirani, and Vazirani (STOC 1990). Motivated by rea…
"Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings
Tomer Ezra, Michal Feldman, Nick Gravin +1
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one…
Oblivious Online Contention Resolution Schemes
Hu Fu, Pinyan Lu, Zhihao Gavin Tang +4
Contention resolution schemes (CRSs) are powerful tools for obtaining "ex post feasible" solutions from candidates that are drawn from "ex ante feasible" distributions. Online cont…
Online Facility Location with Predictions
Shaofeng H. -C. Jiang, Erzhi Liu, You Lyu +2
We provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, demand points arrive in order and the algorithm must irrevocably assign each d…
Secretary Matching with General Arrivals
Tomer Ezra, Michal Feldman, Nick Gravin +1
We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with…
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…
Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models
Tomer Ezra, Michal Feldman, Nick Gravin +1
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arriv…
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the verte…
Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang +1
This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on an…
Online Stochastic Matching with Edge Arrivals
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no online…