arXiv preprint ·
Degree-Parameterized Analysis of Sampling-Based Online Matching
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $θ$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge2$ and $θ\in[0,1]$. The optimal sampling choice interpolates between no sampling for $d=1,2$ and a dense-limit guarantee of approximately $0.2562$, improving on the classical $1/8$ analysis while retaining linear per-arrival time. We also derive worst-case bounds on the variance of the number of matched offline agents, including order-tight behavior as $θ\to1_-$ and an $O(θ)$ bound as $θ\to0_+$ for fixed $m,d$. For \emph{Black-Box Sampling--Matching}, we introduce prefix-dependent reweighting followed by an arbitrary approximate offline matching solver and prove a transfer theorem whose guarantee is the offline approximation ratio times an explicit function of $d$ and $θ$. With exact matching, the framework recovers the classical $1/e$ guarantee in the unbounded-degree limit.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
The Matroid Secretary Conjecture is True
Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.