6 papers
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Pan Xu
The randomized primal-dual framework of Devanur, Jain, and Kleinberg (SODA 2013) splits each unit matching gain between endpoint dual variables according to the matched offline ran…
Online Matching under KIID: Enhanced Competitive Analysis through Ordinary Differential Equation Systems
Pan Xu
We consider the (offline) vertex-weighted Online Matching problem under Known Identical and Independent Distributions (KIID) with integral arrival rates. We propose a meta-algorith…
Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the Upper Bound
Pan Xu
We revisit the classical analysis of Karp, Vazirani, and Vazirani (KVV, STOC~1990), which established the well-known upper bound of as the limiting proportion of vertices…
Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option
Yohai Trabelsi, Pan Xu, Sarit Kraus
Assigning tasks to service providers is a frequent procedure across various applications. Often the tasks arrive dynamically while the service providers remain static. Preventing t…
Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms
Pan Xu
In this paper, we propose an online-matching-based model to tackle the two fundamental issues, matching and pricing, existing in a wide range of real-world gig platforms, including…
Two-Sided Capacitated Submodular Maximization in Gig Platforms
Pan Xu
In this paper, we propose three generic models of capacitated coverage and, more generally, submodular maximization to study task-worker assignment problems that arise in a wide ra…