17 citations · 95 across the 34 of their papers we have counts for
7 papers · 1 filter
Tight Approximation Ratio of Anonymous Pricing
Yaonan Jin, Pinyan Lu, Qi Qi +2
We consider two canonical Bayesian mechanism design settings. In the single-item setting, we prove tight approximation ratio for anonymous pricing: compared with Myerson Auction, i…
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…
Tight Revenue Gaps among Simple Mechanisms
Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang +1
We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessari…
Monopoly pricing with buyer search
Nick Gravin, Zhihao Gavin Tang
In many shopping scenarios, e.g., in online shopping, customers have a large menu of options to choose from. However, most of the buyers do not browse all the options and make deci…
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…