5 citations · 17 across the 10 of their papers we have counts for
4 papers · 1 filter
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…