5 citations · 17 across the 10 of their papers we have counts for
18 papers
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…
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs
Enze Sun, Zonghan Yang, Yuhao Zhang
We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed…
Fair -Center: a Coreset Approach in Low Dimensions
Jinxiang Gan, Mordecai Golin, Zonghan Yang +1
Center-based clustering techniques are fundamental in some areas of machine learning such as data summarization. Generic -center algorithms can produce biased cluster representa…
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…
Survivable Network Design Revisited: Group-Connectivity
Qingyun Chen, Bundit Laekhanukit, Chao Liao +1
In the classical survivable network design problem (SNDP), we are given an undirected graph with costs on edges and a connectivity requirement for each pair of v…
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…
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
Chao Liao, Qingyun Chen, Bundit Laekhanukit +1
In the -connected directed Steiner tree problem (-DST), we are given an -vertex directed graph with edge costs, a connectivity requirement , a root a…
Online Food Delivery to Minimize Maximum Flow Time
Xiangyu Guo, Shi Li, Kelin Luo +1
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the o…
Adwords in a Panorama
Zhiyi Huang, Qiankun Zhang, Yuhao Zhang
Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the online matching problem and gave an optimal -competitive algorithm. Fifteen yea…
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…
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…
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei +1
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G=(V, E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connect…
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…