3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DC2024
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…