4 papers · 1 filter
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…
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…