PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Matching in Convex Bipartite Graphs

Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu

arXiv:2609.05057v1cs.DS

TL;DR

The paper asks whether ordered, interval-constrained resource allocation can improve online matching guarantees. It proves convexity alone does not beat 1−1/e, then introduces Flip for uniform-length intervals, obtaining a 2/3 guarantee with one-bit commitment. The uniform-length optimum remains between 2/3 and 3/4 because no randomized algorithm can exceed 3/4.

  • Problem

    The paper asks whether convexity in the offline resource order can improve online matching beyond the general-graph guarantee of 1−1/e.

  • Method

    The paper analyzes convex bipartite matching and, for requests with exactly d consecutive feasible resources, mixes earliest-feasible and latest-feasible assignment through Flip’s single ex-ante random choice.

  • Results

    Flip is 2/3-competitive in the uniform-length model and tight for Flip, while no randomized online algorithm can achieve a ratio strictly larger than 3/4.

  • Takeaways & Limitations

    Convexity alone retains the 1−1/e worst-case barrier, whereas uniform-length flexibility permits a transparent one-bit policy that surpasses it.

  • Takeaways & Limitations

    The model assumes a known offline resource order and irrevocable online assignments, and the proxy analysis requires overlapping proxies rather than pairwise disjointness.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies online matching when requests have interval neighborhoods over an ordered offline resource pool. Convexity alone preserves the 1−1/e barrier, while uniform-length intervals enable Flip, a one-bit mixture of earliest- and latest-feasible assignment with a 2/3 guarantee.

  • Problem setting: Convex bipartite matching models irrevocable assignments of sequential requests to compatible resources arranged in a known offline order.Each request reveals its neighborhood on arrival and must be matched immediately or left unmatched.
  • General convex model: Convexity alone does not improve the optimal worst-case competitive ratio, which remains 1−1/e.No algorithm can achieve a ratio strictly larger than 1−1/e, matching Ranking’s guarantee for general bipartite graphs.
  • Uniform-length model: In the uniform-length model, every request accepts exactly d consecutive resources, a restriction motivated by standardized service windows and procedural fairness.This model can surpass the 1−1/e barrier with a transparent randomized policy using one random bit.
  • Deterministic baselines: Each deterministic policy is only d/(2d−1)-competitive in the worst case, converging to 1/2 as d grows.Both policies are work-conserving and serve requests whenever compatible capacity remains, yet directional bias can waste resources needed by later requests.
  • Flip: Flip commits before arrivals to either earliest-feasible or latest-feasible assignment, using one fair coin rather than re-randomizing each request.The two policies correspond to assigning the smallest or largest currently available feasible resource.
  • Guarantees: Flip is 2/3-competitive for uniform-length instances, remains valid against a semi-adaptive adversary, and is tight for Flip.Its expected service is at least (2d−1)/(3d−2) times a clairvoyant optimum; no randomized algorithm can exceed 3/4.

2 Preliminaries

The paper models online matching with ordered offline resources and interval neighborhoods, then specializes to requests with exactly d consecutive feasible resources. It establishes that without uniform lengths, convexity alone does not improve the 1−1/e guarantee.

  • Online requests arrive adversarially and must be irrevocably matched to available compatible offline resources or left unmatched.
  • The offline resources are ordered, and every online request has a consecutive interval neighborhood under the convexity assumption.
  • In the uniform-length model, each request has exactly d consecutive offline neighbors, with d ≥2.
  • When neighborhood lengths may vary, every online algorithm has competitive ratio at most 1−1/e.
  • Online vertices may be indexed by nondecreasing left endpoints, and uniform length then also orders their right endpoints.

3 A Simple Randomized Algorithm: Flip

Flip randomly commits to earliest- or latest-feasible matching, and its analysis reduces adversarial performance to the two deterministic rules on structured arrival orders. The paper proves a 2/(?) guarantee in the supplied passages only as the displayed theorem fragment “2d−1,” while identifying unmatched vertices through bad indices of an offset function.

  • Flip uses one random bit to choose uniformly between earliest-feasible and latest-feasible assignment.The selected rule then irrevocably assigns each arrival to its smallest- or largest-indexed available feasible resource.
  • The semi-adaptive adversary chooses the graph, observes Flip’s sampled rule, and then chooses the arrival order.The expected matching size can therefore be analyzed using potentially different arrival orders for the two sampled rules.
  • Theorem 3.1 states that Flip is 2d−1-competitive against the semi-adaptive adversary.
  • For analysis, it suffices to consider graphs with a maximum matching covering every online vertex, so OPT = |V| = n.
  • The canonical greedy matching M⋆ is maximum, and reversing the vertex order makes each deterministic rule’s corresponding order worst-case for the opposite rule.
  • The offset function and its bad indices connect unmatched vertices under the two rules to one-sided local extrema.Every down-matching loss is associated with an H-bad index, while every up-matching loss is associated with an L-bad index.

4 Bounding the Number of Bad Indices

The analysis bounds the total number of H- and L-bad indices by grouping them into maximal chains and packing chain proxies across two tracks. The resulting inequality yields the stated competitive guarantee for every admissible offset function.

  • Setup: The proof applies to any offset function f:[n]→[d] satisfying f(i+1)≤f(i)+1, without requiring that f arise from a graph.This isolates the combinatorial argument from the original matching instance.
  • Chain structure: Maximal H- and L-chains partition the bad indices, have length at most d−1, and same-type chains are separated by at least d+1 indices.Chains are formed from consecutive bad indices whose gaps are at most d.
  • Chain interactions: When an L-chain and a preceding H-chain are within distance 2d, their combined length is at most d−1.The interaction bound follows by comparing the integer-valued offset function at indices in the chains' overlapping region.
  • Proxy motivation: Separate bounds on H and L would yield only a competitive ratio approaching 1/2, so the proof must account for their interactions jointly.The individual bounds can each be tight, but not simultaneously on the same hard instance.
  • Two-track packing: A two-track proxy packing gives each chain total proxy size 3·len(C)+1, while every index is covered at most twice.Same-type extended proxies are disjoint, each proxy overlaps at most one other proxy, and the resulting counting inequality supports the theorem.
  • Main result: Theorem 4.6 establishes a (3d−2)-competitive guarantee against the semi-adaptive adversary.The proxy-size inequality is converted into the final bound on |H|+|L|.

5 Tightness and Impossibility Results

The section proves that Flip’s 2/3 guarantee is tight, while no randomized online algorithm can exceed 3/4 in the uniform-length model.

  • 5.1 Tightness of Flip: Flip has competitive ratio (2d−1)/(3d−2), which converges to 2/3 as d grows.The hard instance exists for every integer d ≥2.
  • 5.1 Tightness of Flip: The hard instance uses 3d−2 offline and online vertices with an adversarial arrival order that leaves only one shared resource for the final block.Under either matching rule, the first two blocks match 2d−2 vertices, and d−1 final-block requests remain unmatched.
  • 5.1 Tightness of Flip: Both realizations admit a perfect matching of size 3d−2, establishing the upper-bound comparison against OPT.The perfect matching is {(u_i,v_i): i ∈[3d−2]}.
  • 5.2 A 3/4 Upper Bound for Any Algorithm: No randomized online algorithm has competitive ratio strictly larger than 3/4 in the uniform-length model.The proof uses two equally likely continuations of a common first phase and Yao’s minimax principle.
  • 5.2 A 3/4 Upper Bound for Any Algorithm: The upper-bound construction partitions offline resources into consecutive blocks and gives every request an interval of exactly d consecutive neighbors.Each realization has n/2 online vertices in each phase, and both realizations admit perfect matchings of size n.

6 Without the Uniform-Length Assumption

The paper shows that dropping the uniform-length assumption restores the general worst-case barrier of 1−1/e, using a recursive convex hard-instance construction.

  • 6 Without the Uniform-Length Assumption: Convexity alone does not improve the worst-case competitive ratio beyond 1−1/e.This matches the classic guarantee achieved by Ranking on general bipartite graphs.
  • 6 Without the Uniform-Length Assumption: The construction adapts the classic upper-triangular hard instance by recursively replacing resources with consecutive blocks.The resulting neighborhoods remain intervals, but their lengths vary across requests.
  • 6 Without the Uniform-Length Assumption: Every neighborhood produced by the recursive construction is an interval, and the instance admits a perfect matching of size m!.At each recursive call, level-k requests can be matched to the dropped interval, whose vertices receive no future neighbors.
  • 6.2 Bounding the Fractional Matching: Applying the recurrence to the recursively generated instance yields the 1−1/e upper bound as m tends to infinity.The proof passes through a harmonic-sum limit and then establishes Theorem 6.1.
  • 6.2 Bounding the Fractional Matching: The analysis tracks average matched fractions through a recurrence w_k(x) that upper-bounds the final average load even for nonuniform allocations.Uniform allocation raises the average by at most 1/k before one subinterval is dropped and the others recurse.

Declaration for the Use of AI

The authors state that the main algorithmic framework was developed by humans, with GPT-5.6 Sol used during exploration of part of the proofs.

  • Declaration for the Use of AI: The authors report that humans fully discovered the main algorithmic framework and independently verified all arguments.The manuscript was written entirely by the authors, who take responsibility for its content.
  • Declaration for the Use of AI: GPT-5.6 Sol was used during exploration for part of the proofs.The declaration distinguishes exploratory use from authorship and verification.
Loading 2609.05057v1…