17 citations · 95 across the 34 of their papers we have counts for
23 papers · 1 filter
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…
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…
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…
(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…
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…
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…
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
There has been a long history for studying randomized greedy matching algorithms since the work by Dyer and Frieze~(RSA 1991). We follow this trend and consider the problem formula…
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang +3
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive on…
Online Makespan Minimization: The Power of Restart
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang +2
We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competit…
Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching probl…
How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang +3
We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices…