Surpassing the Greedy Limit in Online Matching

23 concepts17 papers1 proposal

In online bipartite matching and resource allocation, items or agents arrive sequentially, and an algorithm must make irrevocable matching decisions on the fly. The classic baseline for these problems is the greedy algorithm: whenever an option appears, take the best available match.

While intuitive, greedy strategies suffer from a fundamental flaw: local optimization blinds them to future opportunities. If an algorithm greedily matches a resource to a low-value incoming agent, it cannot un-match that resource later when a high-value agent arrives. Because of this, under adversarial arrival sequences, simple greedy strategies are strictly bounded by a competitive ratio of $0.5$—meaning they can guarantee at most half the value of an omniscient offline solver. As noted by Guy Blanc in Multiway Online Correlated Selection, surpassing this $0.5$ threshold in edge-weighted settings has long been a major open challenge because the algorithm must commit without knowing the weights or timing of future arrivals.

This performance ceiling is not unique to standard matching. In online coverage problems, simple greedy strategies can even drop to a competitive ratio of zero if they exhaust limited capacities on redundant inputs early on, as discussed in Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations.

The Geometry of the Barriers

To understand why these barriers exist, we must look at how information is revealed to the algorithm. There are two primary arrival models: vertex arrival (where an entire node and its incident edges appear at once) and edge arrival (where individual edges appear one by one).

Edge arrival is inherently more difficult. As shown by Buddhima Gamlath et al. in Online Matching with General Arrivals, the competitive ratio for edge arrival models faces a hard ceiling of $1/2$, a limit that persists even for randomized algorithms. Danny Segev et al. further quantified this barrier in Online Algorithms for Maximum Cardinality Matching with Edge Arrivals, establishing a strict upper bound of approximately $0.5914$ for any fractional or randomized algorithm, even on simple tree structures.

When vertices arrive instead of edges, the theoretical ceiling shifts to $1 - 1/e \approx 0.632$. This threshold represents the maximum efficiency achievable by standard algorithms under worst-case vertex sequences. Deterministic algorithms are particularly vulnerable; as proven by Mengjing Chen et al. in A Competitive Analysis of Online Failure-Aware Assignment, deterministic logic cannot guarantee more than half of the optimal offline performance because an adversary can always exploit its predictable nature.

Breaking the 0.5 Barrier via Strategic Ordering

How do we escape the $0.5$ trap? One powerful insight is that while we cannot control the future, we can sometimes control the structure of our choices.

Consider a game where a designer sets a priority order over items, and an adversary subsequently chooses the arrival order of buyers. In Max-min greedy matching (and its extended analysis in Max-Min Greedy Matching), Alon Eden et al. demonstrated that by strategically ordering the items, the designer can always guarantee a matching size strictly greater than half the optimal (specifically, $>0.51$). This subtle shift from a purely passive greedy approach to a proactive, max-min priority framework breaks the long-standing theoretical floor.

Another approach applies to reusable resources, such as ride-sharing vehicles or hotel listings. In Periodic Reranking for Online Matching of Reusable Resources, Rajan Udwani introduced the Periodic Reranking (PR) algorithm. Instead of sticking to a static priority rule that an adversary can easily exploit, the algorithm refreshes resource priorities on a fixed schedule tied to their recovery or "cool-down" times, achieving a competitive ratio of $0.589$.

For settings with structured weights, Moses Charikar et al. investigated "decomposable weights"—where edge weights are products of an offline speed and an online size. In Online Bipartite Matching with Decomposable Weights, the authors showed that while deterministic algorithms face a ceiling of $0.618$, a randomized approach can achieve a competitive ratio of $0.5664$, pushing past the $0.5$ barrier.

Exploiting Statistics and Random Arrivals

If the adversary's power to choose the worst possible sequence cements these barriers, changing the arrival model or leveraging historical data can dissolve them.

When the arrival sequence is random rather than adversarial, the $1 - 1/e$ barrier can be broken. In Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals, Zhiyi Huang et al. designed a two-dimensional randomized primal-dual framework that achieves a competitive ratio of $0.6534$.

Alternatively, if we possess offline statistics about the arrival distribution, we can guide online actions using global information. Vahideh H. Manshadi et al. demonstrated this in Online Stochastic Matching: Online Actions Based on Offline Statistics. By using Monte Carlo sampling to extract statistics from an optimal offline solver, they developed an adaptive algorithm that achieves a competitive ratio of $0.702$, shattering the $1 - 1/e$ barrier.

Similarly, in the context of gig economy platforms, the authors of Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms analyzed attenuation-based sampling policies, proving they hit an optimal competitive ratio of $1/2$ while strictly bounding variance under known heterogeneous arrival distributions.

Even under adversarial conditions, introducing a temporal buffer can help. In Edge Weighted Online Windowed Matching, Itai Ashlagi et al. studied agents who tolerate a deadline window before departing. They showed that a randomized "Postponed Greedy" algorithm secures at least $25\%$ of the optimal weight under adversarial arrivals, which improves to $0.279$ when arrivals occur in a random order.

Generalizing the Limits of Determinism

The tension between deterministic vulnerability and randomized resilience extends far beyond matching into broader online resource allocation problems, such as bin packing, knapsack problems, and rent-or-buy dilemmas.

In the online knapsack problem, deterministic algorithms are fundamentally intractable when making irrevocable decisions without future knowledge, often failing to guarantee any constant performance ratio. However, as shown by Lukasz Jez et al. in Online Knapsack Revisited, introducing multiple bins or randomization makes these problems solvable with constant competitive ratios. For bin covering, Carsten Fischer et al. proved in Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering that while simple single-bin-at-a-time strategies are capped at a $2/3$ competitive ratio across all distributions, average-case performance under random arrival orders often matches independent and identically distributed (i.i.d.) performance, bypassing worst-case limitations.

In problems with complex cost structures, like energy plan selection or ski rental, deterministic logic similarly hits a wall. Jianing Zhai et al. showed in Stay or Switch: Competitive Online Algorithms for Energy Plan Selection in Energy Markets with Retail Choice that deterministic algorithms face a strict performance floor (a competitive ratio of 3) when navigating switching costs and tariffs.

To hedge against these worst-case sequences, researchers have turned to randomized and learning-augmented frameworks. For instance, Yongho Shin et al. developed a randomized strategy in Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis that leverages machine learning predictions while maintaining a rigorous safety net, bypassing the rigid limits of purely deterministic choices.

Key Foundational Work

Online Bipartite Matching with Decomposable Weights (2014) — contributed 2 concept elements to this direction.
Online Stochastic Matching: Online Actions Based on Offline Statistics (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_greedy_matching_lower_bound_c71dc9ab,
  title = {greedy matching lower bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-matching-lower-bound/rdr_c71dc9abeb754e05887ae1386abb9016},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_greedy_matching_lower_bound_c71dc9ab_v1,
  title = {greedy matching lower bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-matching-lower-bound/rdr_c71dc9abeb754e05887ae1386abb9016/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake