CS Paper Radar

Beating One Half for Online Bipartite Matching with Reusable Resources

Xiaohui Bei, Zhihao Gavin Tang, Wenhao Wu

cs.DS ·submitted 2026-10-01 16:29 UTC · v1
benchmarktheory

Abstract

We study online bipartite matching with unit-inventory reusable resources, where requests arrive in an adversarially fixed order, and each use of a resource makes it unavailable for an independent duration drawn from a resource-dependent distribution. The benchmark knows all requests in advance but cannot observe a duration before choosing the corresponding use. The classical Ranking algorithm of Karp, Vazirani, and Vazirani (STOC 1990) fixes a uniformly random priority order of the resources and matches each arriving request to its highest-priority available neighbor. It achieves the optimal competitive ratio $1-1/e$ for unweighted nonreusable resources, but whether it beats $1/2$ for reusable resources has remained open. We prove that, for unweighted resources with resource-dependent stochastic durations, Ranking achieves a competitive ratio of $(5-2\sqrt3)/3\approx0.511966$. We also give a black-box reduction from unweighted Ranking to resource-weighted matching: any unweighted competitive ratio $α>1/2$ yields a weighted ratio strictly above $1/2$. With independent sampling access to the duration distributions, the reduction gives a weighted ratio of $0.500034$. These results resolve two questions left open by Delong et al. (MOR 2024): whether Ranking beats $1/2$, and whether one can beat $1/2$ under stochastic durations. We analyze Ranking resource by resource, rather than request by request. For deterministic durations, this gives a reduction to random-order greedy for a coverage function. We then extend the analysis to stochastic durations by comparing the residual schedules of Ranking and a greedy algorithm, and apply a finer analysis of the random ranks to obtain the stated $0.511$ bound. For the weighted reduction, we apply Ranking within groups of similar weights and uses weighted greedy to control the loss between groups.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.78
Abstract · 29 pages

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs under irrevocable decisions and adversarial arrivals. We first show that convexity alone does not improve the classic worst-case guarantee of 1-1/e, achieved by Ranking. We then consider the uniform-length model, in which every online request has exactly d consecutive offline neighbors. We propose Flip, which uses one random bit to commit ex-ante to either earliest-feasible assignment or latest-feasible assignment. Although either natural deterministic policy can waste capacity and be asymptotically only 1/2-competitive, we show that their randomized mixture is 2/3-competitive. This guarantee is tight for Flip and remains valid against a semi-adaptive adversary that observes the selected policy before choosing the arrival order. We also prove that no randomized online algorithm can achieve a competitive ratio strictly larger than 3/4 in the uniform-length model.

0.10

Online Matching with Arbitrary Stochastic Rewards

cs.DS math.OC ·2026-11-02 ·Rajan Udwani
benchmark similarity 0.75
Abstract

Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

0.07

Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching

cs.GT cs.DS ·2026-09-28 ·Arghya Chakraborty, Varun Gupta
similarity 0.73
Abstract · Appearing in WINE 2026

In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care only about receiving service (matched vs. unmatched) and not which offline resource serves them, while the platform's objective is to maximize total matching reward. This captures applications such as ride-sharing where the users primarily care about being matched to a ride while the platform internalizes the cost of dispatching a distant driver; dispatching homogeneous service requests to heterogeneous servers (cloud/edge routing); and assigning customer requests to a pool of providers with different flexibility (e.g., English-only vs. bilingual agents). Our main question is: \textit{Is constant-competitive matching possible for incentive-compatible, random-order edge-weighted matching on complete bipartite graphs?} Motivated by the LP-based treatment of incentive compatibility in the classical secretary problem by Buchbinder et al., we impose a constraint that the ex ante probability of selection is equalized across all arrival positions. We answer our main question in the affirmative and propose the first constant-competitive algorithm for incentive compatible edge-weighted random-order online matching on complete bipartite graphs. The competitive ratio of our algorithm is parameterized by the imbalance factor $k := n/m$ -- where $n$ and $m$ are the numbers of online and offline nodes, respectively, and $k$ is a positive integer. In particular, we obtain a competitive guarantee of the form $c_k - O(1/\sqrt{m})$ where $c_1 \approx 0.162$ and $c_k \to 0.02308\ldots$ as $k \to \infty$. We also present algorithms with strictly improved competitive ratio of $\approx 0.07 + O(1/m)$ for the binary-weighted case ($0$-$1$ rewards).

0.05

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.72
Abstract

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

0.37

Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking

cs.DS cs.GT ·2026-10-13 ·Pan Xu
similarity 0.71
Abstract

The randomized primal-dual framework of Devanur, Jain, and Kleinberg (SODA 2013) splits each unit matching gain between endpoint dual variables according to the matched offline rank. The gain-sharing function affects the certificate but not Ranking's decisions. Keeping the splitting rule and expected edgewise feasibility criterion fixed, we define certifying capacity as the strongest uniform guarantee obtainable by functional optimization over a prescribed function class. Its shortfall from Ranking's actual competitiveness is the certifying gap. We study unweighted online bipartite matching under adversarial arrivals on graphs with online degree at most $d$ and on $d$-regular graphs. The optimized protocol is tight on both degree-one classes and in the unrestricted setting, but has a strictly positive gap on both degree-two classes, even over all measurable nonnegative complementary splits. In both degree-two settings, we determine Ranking's exact competitiveness and the exact certifying capacity over nondecreasing gain-sharing functions. For general $d$, we optimize over nondecreasing, right-continuous functions $f:[0,1]\to[0,1]$ with $f(1)=1$, using their probability-measure representation. Both the certifying capacity and actual competitiveness converge to $1-1/e$ in both instance families as $d\to\infty$. The resulting gap is at most $1/(2ed)+O(d^{-2})$ for online degree at most $d$; on $d$-regular graphs, it vanishes but is at least $(1/(2e)-o(1))/d$. These results distinguish function-class restrictions from limitations of the fixed protocol and motivate tighter randomized primal-dual frameworks.

0.15

Improved Bounds for Online Matching with Random Edge Arrivals

cs.DS ·2026-11-10 ·Yilong Feng, Haolong Li, Zonghan Yang
similarity 0.71
Abstract

We study the unweighted online matching problem with random edge arrivals, where each edge arrives at an independent time drawn uniformly from $[0,1]$, and the algorithm must immediately and irrevocably accept or reject it while maintaining a matching. Guruganesh and Singla (IPCO, 2017) first broke the $1/2$ barrier of the naive Greedy algorithm by giving a $(1/2+\varepsilon)$-competitive algorithm for a small constant $\varepsilon>0$, a guarantee that has remained the best known for nearly a decade. We give a simple three-phase algorithm that achieves a competitive ratio of $0.5445$ by deliberately rejecting selected early edges to reserve their endpoints for later matching opportunities. With a different choice of parameters, the same algorithm is $0.5535$-competitive on triangle-free graphs, including bipartite graphs. We also establish competitive ratio upper bounds below $0.6964$ for general graphs and $0.7043$ for bipartite graphs via exact rational evaluation of an optimal-policy recurrence on fixed graphs, even when the input graph is known up to isomorphism.

0.22

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory similarity 0.70
Abstract

In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].

0.28

Degree-Parameterized Analysis of Sampling-Based Online Matching

cs.DS cs.GT ·2026-09-13 ·Pan Xu
publishedtheory similarity 0.70
Abstract · A preliminary version of this work has been accepted to WINE 2026

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.

0.28