arXiv preprint ·
Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.
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
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Improved Algorithms for the Remote Point Problem
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Exponential Quantum Advantage in Testing Fourier Dimensionality
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.