Showing 2025Show all
2 papers · 1 filter
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…