PaperlayerView exact revision on arXiv

Source-linked AI summary

Beating One Half for Online Bipartite Matching with Reusable Resources

Xiaohui Bei, Zhihao Gavin Tang, Wenhao Wu

arXiv:2610.01993v1cs.DS

TL;DR

The paper asks whether Ranking can beat 1/2 for online matching with reusable resources and stochastic durations. It analyzes Ranking resource by resource and proves an unweighted ratio of (5-2√3)/3, with a reduction that extends any unweighted guarantee above 1/2 to weighted matching.

  • Problem

    Whether Ranking can beat 1/2 for reusable resources, including with resource-dependent stochastic durations, has remained open.

    Source: §1 · p. 2

  • Method

    The analysis views Ranking resource by resource, compares residual schedules under stochastic durations, and uses a rank cut; a black-box reduction transfers unweighted guarantees to weighted matching.

    Source: §1.1 · p. 3, §1.2 · p. 4, §6 · p. 23

  • Results

    (5-2√3)/3 is the unweighted Ranking ratio, and an unweighted guarantee α > 1/2 yields a weighted ratio strictly above 1/2.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Takeaways & Limitations

    A single random priority order suffices to beat 1/2 for unweighted reusable resources with resource-dependent i.i.d. durations.

    Source: §6 · p. 23

    The tight ratio for Ranking remains open, and whether weighted matching can beat 1/2 without duration-distribution sampling is unresolved.

    Source: §6 · p. 23

Abstract

from arXiv · show

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 $\alpha>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.

1 Introduction

The paper asks whether Ranking can beat 1/2 for reusable resources with heterogeneous or stochastic durations. It establishes an unweighted guarantee above 1/2 and a black-box route to a weighted guarantee above 1/2.

1 Introduction

  • The open questions concern whether Ranking beats 1/2 for reusable resources, including under heterogeneous deterministic or resource-dependent stochastic durations.In this model, assignments trade current reward against future resource availability, while durations add uncertainty about release times.Source: §1 · p. 2

1.1 Our Results

  • (5-2√3)/3 is the competitive ratio established for unweighted Ranking with resource-dependent i.i.d. durations.The analysis also covers deterministic durations as a special case.Source: §1.1 · p. 3, §1.2 · p. 4
  • Any unweighted Ranking guarantee α > 1/2 yields a randomized weighted algorithm with a ratio strictly above 1/2.The reduction groups similar weights and filters active edges; it preserves only part of the unweighted improvement.Source: §1.1 · p. 3, §1.2 · p. 4

1.2 Technical Overview

  • A resource-by-resource view turns deterministic Ranking into random-order greedy for a coverage function and supports a stochastic residual-schedule comparison.A rank cut supplies an additional inequality that improves the stochastic guarantee beyond 1/2.Source: §1.2 · pp. 3–4

1.3 Related Work

  • Unlike prior weighted-greedy guarantees that improve on 1/2 only when immediate-return probability is bounded away from zero, this guarantee is uniform over resource-dependent i.i.d. durations.The paper also relates its deterministic coverage reduction to random-order submodular maximization.Source: §1.3 · pp. 4–5

2 Model and Preliminaries

The model assigns sequential requests to compatible, currently available resources whose uses temporarily remove them for resource-dependent i.i.d. durations. Ranking uses one random resource order and assigns each request to its highest-priority available compatible resource; the benchmark is nonanticipatory but knows the instance in advance.

2 Model and Preliminaries

  • Each use earns resource reward c_v and makes that resource unavailable for an independent duration drawn from its resource-dependent distribution D_v.The unweighted case sets every c_v to 1; resource-weighted rewards may differ.Source: §2 · p. 5
  • The benchmark knows the request sequence, compatibility graph, rewards, and duration distributions, but commits to each use before observing its duration.It processes requests chronologically and may adapt to durations observed from earlier uses.Source: §2 · p. 5
  • An algorithm is ρ-competitive when its expected reward is at least ρ times the benchmark’s expected reward on every instance.Durations can be truncated at T + 1 for analysis without changing within-horizon availability decisions.Source: §2 · p. 6
  • Ranking samples a uniformly random resource permutation before requests arrive and assigns each request to its highest-priority available compatible resource, if one exists.Equivalently, it gives resources independent uniform ranks and chooses an available compatible resource of minimum rank.Source: §2 · p. 6

3 Warm-Up: Deterministic Durations

For deterministic durations, processing resources in priority order turns Ranking into greedy selection for a coverage problem. The reduction yields a 0.5096 competitive guarantee for arbitrary resource-dependent deterministic durations.

3.1 Resource-by-Resource Execution

  • Processing resources from highest to lowest priority and scanning requests not already assigned produces the same matching as chronological fixed-priority greedy.The equivalence holds for every priority order and duration realization, including stochastic durations once their values are fixed.Source: §3.1 · p. 6

3.2 Reduction to Coverage Maximization

  • The deterministic matching problem has the same optimum as a coverage problem whose objective is monotone coverage and whose constraint is a partition matroid.A resource’s feasible schedules form its class; choosing a schedule adds the requests it covers that were not covered earlier.Source: §3.2 · p. 7
  • The earliest feasible scan maximizes the number of uncovered requests served by a resource, so the resource-by-resource execution makes a maximum-marginal choice in each class.The class order is uniformly random, while requests remain in adversarial order.Source: §3.2 · pp. 7–8
  • 0.5096-competitive: Ranking achieves this guarantee for arbitrary resource-dependent deterministic durations.The guarantee follows by reducing the matching problem to random-order greedy for a monotone submodular coverage function under a partition matroid constraint.Source: §3.2 · p. 8

4 Stochastic Durations

For stochastic durations, the analysis replaces the fixed-schedule coverage reduction with an expected residual-schedule comparison. It then tracks benchmark requests by owner and rank, using a cut in the random priority order to establish a guarantee above 1/2.

4 Stochastic Durations

  • The deterministic reduction cannot be applied literally before stochastic duration samples are realized, because there is no fixed family of feasible schedules at that point.The resource-by-resource representation remains valid after samples are fixed and motivates the stochastic substitute.Source: §4 · p. 8

4.3 Comparison across a Rank Cut

  • The analysis combines three inequalities to cancel early-capture losses and establish a Ranking guarantee above the 1/2 baseline.The owner accounting already identifies improvement when sufficiently many benchmark requests are captured at or after their owners; the rank cut supplies an additional inequality.Source: §4 · p. 8, §4.2 · p. 9, §4.3 · p. 15

4.1 Residual Schedule Comparison

  • The earliest feasible scan serves at least as many requests in expectation as the residual part of any independent nonanticipatory schedule on an independently specified remaining request set.This residual-schedule comparison remains valid after conditioning on external randomness that fixes the removed set, provided the required independence is retained.Source: §4.1 · p. 8

4.2 Benchmark Owners and Rank Densities

  • Owner accounting separates benchmark requests captured before their owners from those captured at or after their owners, tracking total, early, and late capture densities.Early captures create immediate gains but remove requests from an owner’s later benchmark comparator; late captures create no such later loss.Source: §4.2 · p. 10

4.3 Comparison across a Rank Cut

  • A cut at rank p compares Ranking with an independent execution on the remaining resources to bound useful auxiliary coverage still available after the cut.The useful mass counts benchmark requests owned by resources processed by p that remain unserved by the main execution and covered by an auxiliary resource still unprocessed.Source: §4.3 · pp. 12, 14

5 Weighted Resources

This section develops a black-box reduction from unweighted Ranking guarantees above 1/2 to weighted guarantees, combining sparse randomized Ranking within comparable-weight buckets with weighted-greedy reward from inactive buckets. It gives an explicit weighted guarantee of 0.500034.

5.1 Weighted-Greedy Baseline

  • Weighted greedy earns at least M/2, and the excess slack σ = 2G − M bounds the comparison terms used to control filtering loss.The analysis links filtering loss to how far weighted greedy exceeds its 1/2 benchmark guarantee.Source: §5.1 · pp. 15–16

5.2 Random Weight Buckets and the Algorithm

  • Randomly shifted geometric weight buckets activate independently; active buckets run Ranking on kept edges, while inactive buckets follow weighted greedy.Filtering permits cross-bucket displacement only when the greedy resource’s reward is less than a θ fraction of the active resource’s reward; sampling preserves feasibility and nonanticipation.Source: §5.2 · pp. 16–17

5.3 Filtering Loss

  • The expected rounded benchmark value lost to filtering is bounded using ηχ(γ)(∆ + B), which weighted-greedy slack controls.A random bucket shift makes separation losses proportional to reward differences; the E and L contributions are bounded by ηχ(γ)∆ and ηχ(γ)B, respectively.Source: §5.1 · p. 15, §5.3 · p. 19

5.4 Reward from Active Buckets

  • Applying the unweighted α guarantee within each active bucket earns active reward against retained benchmark uses, while higher-bucket matches cause bounded interference.A lower owner bucket is active with probability η, and its rounded reward is at most 1/γ of the higher-bucket match, bounding the unavailable benchmark value relative to active reward.Source: §5.4 · pp. 20–21

5.5 Combining Active and Inactive Buckets

  • The analysis begins combining active reward with weighted-greedy reward from inactive buckets, whose activation complement is 1 − η.Source: §5.5 · p. 21
  • Each active match displaces at most one inactive greedy assignment, with displaced reward less than θ times the active resource’s reward.The active edge is kept, and the two resources lie in different buckets.Source: §5.5 · p. 21
  • If Ranking is α-competitive in the unweighted model for α > 1/2, then for sufficiently small ε > 0 depending only on α, the black-box reduction has ratio strictly larger than 1/2.When its coefficient is nonnegative, the instance-dependent term σ ≥ 0 can be dropped because it only improves the bound.Source: §5.5 · pp. 21–22

5.6 Numerical Parameters

  • The excerpt states M = 0.500034 M, identifies α0 as a valid unweighted guarantee, and says that (33) holds before Theorem 5.6 yields its result.Source: §5.6 · p. 22

6 Discussion

A single random priority order gives Ranking a ratio above 1/2 for unweighted reusable resources with resource-dependent stochastic durations. The discussion identifies the weighted extension and the tight ratio of Ranking as open directions.

6 Discussion

  • Ranking beats 1/2 for unweighted reusable resources, even with arbitrary resource-dependent i.i.d. durations.The result uses a single random priority order.Source: §6 · p. 23
  • The analysis views each resource as serving requests left by higher-priority resources, using coverage-function random-order greedy for deterministic durations and residual-schedule comparisons for stochastic durations.Tracking benchmark requests relative to their owners’ ranks yields the improvement over 1/2.Source: §6 · p. 23
  • The weighted reduction shows that an unweighted improvement over 1/2 can yield a weighted guarantee above 1/2.Source: §6 · p. 23
  • The tight competitive ratio remains open even for constant deterministic durations, and weighted guarantees above 1/2 without distribution-sampling access remain unresolved.The nonreusable special case gives an upper bound of 1 − 1/e, leaving a gap from the guarantee.Source: §6 · p. 23

AI Disclosure

The authors disclose that generative AI tools assisted with mathematical development and exposition, while stating they verified the arguments and take responsibility for the final text and results.

AI Disclosure

  • The authors report that GPT 5.6 and GPT 6 assisted mathematical development and exposition, and that the authors verified the arguments and take responsibility for the final text and results.Source: AI Disclosure · p. 23

A Combining the Rank Inequalities

The appendix combines weighted inequalities using nonnegative weights that sum to one, chosen to cancel one coefficient and keep another nonnegative. It verifies these weight properties before applying the resulting inequalities.

A Combining the Rank Inequalities

B Checking the Weighted Constant

This section verifies the claimed weighted-constant improvement through parameter-feasibility checks and strict rational comparisons.

B Checking the Weighted Constant

C Second-Order-Supermodular Welfare

The section extends rank-based analysis to online submodular welfare with normalized, monotone, second-order-supermodular valuations. It tracks how greedy assignments reduce optimal-item contributions and compares these changes across random-rank cuts.

C Second-Order-Supermodular Welfare

  • The proof carries over the three rank inequalities to the second-order-supermodular setting.The argument uses Korula et al.’s item-arrival framework, separately from the deterministic coverage reduction.Source: C Second-Order-Supermodular Welfare · p. 29
  • The analysis establishes a competitive guarantee for online submodular welfare with normalized, monotone, second-order-supermodular valuations.The proof obtains the stated ratio by establishing the same three rank inequalities used in the matching proof.Source: C Second-Order-Supermodular Welfare · pp. 29, 31
  • Each g_i(A) is the remaining contribution of optimal pair o_i after assignments A; these contributions are nonnegative, decreasing, and supermodular.Under second-order supermodularity, the aggregate reduction in contributions of any item set P is a nonnegative monotone submodular function.Source: C Second-Order-Supermodular Welfare · pp. 29–30
  • Across a rank cut, the remaining auxiliary comparison value satisfies Y(p) ≥ qD(p), while its decline reflects both departing unprocessed items and reductions from main assignments.The first effect is normalized by 1 − x; the second is controlled by b(x).Source: C Second-Order-Supermodular Welfare · pp. 30–31
Loading 2610.01993v1…