betaFeedback

WorksComputer Science

Online Edge-Weighted Matching Beyond 0.55

Abstract

We give a 0.5561950.556195-competitive randomized algorithm for edge-weighted online bipartite matching with free disposal, improving the 0.53680.5368 guarantee of Blanc and Charikar. The result holds for arbitrary nonnegative edge weights and any input sequence fixed independently of the algorithm's randomness. Our algorithm builds on online correlated selection, introduced by Fahrbach, Huang, Tao, and Zadimoghaddam, and its multiway extension due to Blanc and Charikar. Our main contribution is a state-dependent primal–dual analysis of correlated selection. At each weight threshold, we track the state of the selection process jointly with an auxiliary failure event. The analysis accounts for arrivals below the threshold, which change the state without improving the matching value at that threshold. A potential function bounds the dual increase in both cases. We instantiate the analysis with an explicit win map that assigns a common score to an initial range of states. Its selection inequalities are verified by a finite computer-assisted proof covering every required candidate multiplicity and every real threshold; the verifiers are available in an accompanying repository. Triangular unit-weight inputs asymptotically attain the guarantee of the underlying ideal algorithm, proving that its analysis is tight.

Introduction

Online bipartite matching asks how much of an optimal allocation can be recovered when one side of the graph is revealed over time. For unweighted matching, the Ranking algorithm of Karp, Vazirani, and Vazirani [13] achieves the optimal competitive ratio 1−1/e1 - 1/e. The same ratio is attainable when weights belong to the offline vertices [1]. With arbitrary edge weights and no free disposal, an early assignment can prevent an arbitrarily more valuable later assignment. Free disposal allows each offline vertex to retain its most valuable assigned edge. This is a natural model for display advertising, where an advertiser may receive several impressions but pays only for its most valuable assignment [7].

Even with free disposal, the greedy 1/21/2 guarantee resisted improvement for more than a decade. Fahrbach, Huang, Tao, and Zadimoghaddam [6] broke this barrier with a 0.5086-competitive algorithm and introduced online correlated selection (OCS). Gao et al. [GHH+22] obtained a 0.519 guarantee, and Blanc and Charikar [2] introduced multiway OCS and obtained 0.5368. The OCS viewpoint separates two tasks. A sampling rule chooses the candidates for the current arrival, and a selection procedure chooses one integral assignment from those candidates. Correlating the selections across arrivals can make repeated requests to a vertex more effective than independent rounding.

For weighted matching, however, a vertex is not simply covered or uncovered. An edge of weight ww can help at every level below ww and at none of the levels above it. A useful selection process must therefore work for many overlapping subsequences of arrivals. Moreover, arrivals outside one such subsequence still advance the process. A competitive analysis must account for these changes of state without charging them to matching gain at that threshold.

We address this issue by keeping the state distribution in the dual analysis. This removes a restriction in the earlier reduction that limits the benefit of sampling many candidates.

Our results

The offline side LL of a bipartite graph is known in advance. Online vertices arrive in an arbitrary fixed order and reveal their incident nonnegative edge weights. Each arrival is assigned to at most one offline vertex. An offline vertex may receive several assignments; only its heaviest assigned edge contributes to the objective. The benchmark OPT is the weight of a maximum matching in the entire input graph. The input is fixed independently of the algorithm’s random choices. Missing edges may be treated as zero-weight edges; an assignment to one is implemented by discarding the arrival.

Theorem 1. There is a randomized 0.556195-competitive algorithm for edge-weighted online bipartite matching with free disposal. For every finite input graph and every fixed arrival order,

E[ALG]≥0.556195 OPT.\mathbb{E}[\mathrm{ALG}] \ge0.556195\ \mathrm{OPT}.

For rational input weights, the algorithm has a finite implementation with expected polynomial running time, with fixed preprocessing depending only on the constant in the guarantee.

The graph-independent preprocessing is large. § 7 gives the constants and their certificates. § 4 gives the finite algorithm, its stored state, and pseudocode for both sampling and assignment. The verification programs and Lean sources are available in the artifact repository.3 Appendix § 12 gives reproduction instructions.

The proof has two components. First, we give a state-dependent primal–dual theorem for a family of geometric-age selection processes. The process records an age: the number of steps since its most recent reset. A win map WW assigns a desired win probability to each output of this process. Let TWT_W be the substochastic matrix that retains only transitions on which an auxiliary selection trial fails, and let π\pi be the stationary age distribution. When WW satisfies the tournament inequalities, the competitive guarantee is

γ(W)=1−1m+1∑n≥0(mm+1)nπTWn1.(1)\gamma(W)=1-\frac{1}{m+1}\sum_{n\geq0}\binom{m}{m+1}^{n}\pi T_W^{n}\mathbf{1}. \tag*{(1)}

Here mm is the number of candidates sampled on an arrival. This expression already appears in Blanc–Charikar’s reduction [2 Theorem 7], under additional shape and gap conditions. To see the restriction imposed by the gap condition, write F(n)=πTWn1F(n)=\pi T_W^n\mathbf{1}. For a map with stationary mean 1/m1/m, we have F(1)−F(0)=−1/mF(1)-F(0)=-1/m. When γ>1/2\gamma>1/2, the gap condition in [2 Equation (23)] requires

m≤1−γ2γ−1,or equivalentlyγ≤m+12m+1.m\leq\frac{1-\gamma}{2\gamma-1}, \qquad\text{or equivalently}\qquad \gamma\leq\frac{m+1}{2m+1}.

This upper bound tends to 1/21/2 as the number of candidates grows. Theorem 4 establishes the same guarantee for the geometric-age family without this restriction or the scalar shape assumptions. Its invariant accounts for intervening arrivals through their effect on the state distribution. Theorem 15 shows that, for maps of stationary mean 1/m1/m with positive baseline, γ(W)\gamma(W) is the exact worst-case ratio of the specified ideal algorithm. A deterministic family of triangular unit-weight graphs attains it asymptotically.

Second, we choose the win map. For fixed mm and reset probability, Theorem 6 characterizes an optimal nondecreasing map under the necessary calibration constraint for a vertex sampled once. It assigns the same baseline score to an initial segment of ages, modifies at most one boundary age, and preserves the remaining quantile-bin scores. The map is explicit once the baseline is fixed. Proposition 9 extends this optimization to a broader class of processes with independent resets by averaging over their internal state conditional on the time since the last reset.

A vertex sampled more than once imposes further selection constraints; the optimization theorem alone does not establish these. We verify them for the map used in Theorem 1. § 7 fixes the constants, Appendix § 9 proves the finite certificate’s sufficiency, and Appendix § 12 identifies the repository verifiers.

Related work

Online matching and free disposal. The OCS literature has developed several ways to correlate online choices while preserving feasible assignments. Gao, He, Huang, Nie, Yuan, and Zhong [GHH+22] strengthened two-way OCS and obtained a 0.519 guarantee. Shin and An [SA21] constructed a three-way OCS, obtaining 0.5093 directly and 0.5132 when combined with the improved two-way OCS. Blanc and Charikar [2] developed multiway OCS and obtained a 0.5368-competitive algorithm. Their reduction also showed that the original two-way formulation cannot give a ratio above 0.5239. For complete bipartite graphs with product-form weights wij=aibjw_{ij}=a_i b_j, Charikar, Henzinger, and Nguyen [3] obtained a 0.5664-competitive algorithm. That result exploits the decomposable weight structure; the theorem here permits arbitrary edge weights on arbitrary bipartite graphs. The surveys of Mehta [14] and Huang, Tang, and Wajc [9] give broader background on the models and techniques of online matching and ad allocation.

Primal–dual analysis and submodular allocation. Devanur, Jain, and Kleinberg [5] gave a randomized primal–dual analysis of Ranking and its vertex-weighted extension, with dual feasibility in expectation. For free disposal, Devanur, Huang, Korula, Mirrokni, and Yan [4] developed an analysis using a level function. The threshold decomposition in the present paper belongs to this line of work and to the complementary cumulative-distribution viewpoint used by Fahrbach et al. [6]. Our dual credit additionally records the joint distribution of the selection state and the event of auxiliary failure. Fractional free-disposal algorithms admit the stronger 1−1/e1-1/e guarantee. Recent treatments include the primal–dual frameworks surveyed by Niazadeh and Udwani [NU26] and the minimax framework of Kesselheim, Molinaro, Patton, and Singla [11]. These fractional guarantees do not supply the integral rounding required here.

Free-disposal matching is a special case of online submodular welfare maximization: the valuation of an offline vertex for its assigned set is the maximum incident edge weight in that set. The special form of these valuations matters. Kapralov, Post, and Vondrák [12] rule out polynomial-time competitive ratios strictly above 1/21/2 for general coverage valuations, unless NP = RP. Udwani and Wajc [UW26] recently proved an unconditional 1/21/2 upper bound for general online submodular welfare in the standard model, where value queries involve already arrived items. Our improvement uses the maximum-weight valuation of matching; it does not extend to arbitrary monotone submodular valuations.

Overview of the Proof

A state-dependent analysis for general edge weights

From weights to coverage. For an offline vertex ii, let MiM_i be the largest weight assigned to it. Its expected contribution is

E[Mi]=∫0∞Pr⁡(Mi≥w) dw.\mathbb{E}[M_i] = \int_{0}^{\infty} \Pr(M_i \ge w)\,\mathrm{d}w.

Thus we can study, simultaneously for every ww, whether an arrival of weight at least ww has selected ii. This complementary cumulative distribution function viewpoint is standard in weighted online matching [4, 6]. It explains why negative correlation is useful: repeated opportunities above a threshold should be less likely to fail together. It also identifies the main obstacle. An arrival below the threshold does not cover it, but it can change the distribution of the next selection opportunity.

The selection process. Give each offline vertex an independent process whose state is its age since the last reset. Each occurrence of the vertex among the sampled candidates advances the process by one step, called an exposure. The age increments with probability q=1−pq = 1 - p and resets to zero with probability pp. A reset at age zz produces a score W(z)W(z), representing a desired win probability; a nonreset produces the baseline b=W(−1)b = W(-1). Write XkX_k for the desired win probability at step kk. We take WW to be nondecreasing: a longer wait before a reset gives a larger score, while a reset returns the process to age zero. This dependence between successive scores is what we use to improve on independent selection.

On each arrival, the algorithm samples mm candidates independently from a probability vector vv. If vertex ii appears rr times, its process takes rr consecutive steps. Its combined desired win probability is 1−∏k=1r(1−Xk)1 - \prod_{k=1}^{r}(1 - X_k). A monotone tournament of Blanc and Charikar [2] converts the combined probabilities into one actual winner. The vector vv is a deterministic function of the input prefix and the averaged states. It is independent of all realized candidate multisets, seed states, and tournament outcomes. Consequently, after conditioning on the candidate multisets, the selection processes retain the dependence properties needed in the analysis.

The tournament bounds the probability that a vertex remains unselected on any fixed set of arrivals by the expected product of its auxiliary failure probabilities. In particular, the bound applies to the arrivals whose edge to that vertex has weight at least a chosen threshold.

The residual potential. Fix a vertex ii and a threshold ww. Let ν(z)\nu(z) be the probability that all auxiliary trials for edges of weight at least ww have failed and the current age is zz. This is a subprobability distribution: its total mass is the current auxiliary failure probability. Write PP for the age transition matrix and TT for the substochastic matrix that also requires the auxiliary trial to fail. On an arrival with edge weight wiw_i, each step sends ν\nu to νT\nu T if w≤wiw \le w_i, and to νP\nu P if w>wiw > w_i.

The state ν\nu records more than its total mass. Two thresholds can have the same failure probability but different age distributions. To account for this difference, continue the auxiliary trials for an independent geometric number of steps with mean mm. Let h(z)h(z) be the probability of at least one success, starting at age zz. Starting at a larger age gives at least as large a success probability at the first reset; after that reset, the processes can be coupled to agree. Thus hh is nondecreasing.

Let π\pi be the stationary age distribution and put γ=πh\gamma= \pi h. The residual potential of the threshold is νh\nu h: the expected success probability that remains on its uncovered mass. We assign the complementary quantity γ−νh\gamma- \nu h as offline dual credit. It starts at zero because initially ν=π\nu= \pi.

Solving the one-step recurrence for the independent stopping experiment gives

h=1−(I−m(T−I))−11.h = 1 - (I - m(T-I))^{-1}\mathbf{1}.

Proposition 5 shows that this choice maximizes πh\pi h among bounded linear potentials satisfying the local update inequality for w≤wiw \le w_i on states satisfying the invariant below.

Credit monotonicity. The proof uses the complementary vector θ=π−ν\theta= \pi- \nu. We show that every reachable θ\theta is a nonnegative linear combination of π\pi and the distributions δ0Pn\delta_0P^n, n≥0n \ge0. The latter is the distribution of a geometric age truncated at nn; it becomes stochastically older when another ordinary exposure is taken. This representation is preserved by both updates. A PP-update advances each component by one age transition. A TT-update also contributes a stationary component from the baseline success probability and a fresh reset component from the additional success probability at a reset. The existing components are rescaled and advanced; all coefficients remain nonnegative. Since each component becomes stochastically older under an age transition, the representation gives θPh≥θh\theta Ph \ge\theta h, equivalently νPh≤νh\nu Ph \le\nu h. Since 0≤T≤P0 \le T \le P and h≥0h \ge0, a TT-update also satisfies νTh≤νPh≤νh\nu Th \le\nu Ph \le\nu h. Thus both updates increase the credit γ−νh\gamma- \nu h. This invariant handles arbitrary interleavings of arrivals above and below the threshold.

The two update inequalities. Suppose the current vertex is sampled with probability xx. Its number of exposures is Bin⁡(m,x)\operatorname{Bin}(m,x). If w≤wiw \le w_i, the updated state is ν(I+x(T−I))m\nu(I + x(T-I))^m. Write y(x)y(x) for its mass and a(x)a(x) for its residual potential. The recurrence defining hh gives

m(T−I)(h−1)=h.m(T-I)(h-1)=h.

After differentiating the binomial update and using the invariant, this identity yields

−y′(x)+a′(x)≥a(x).-y'(x)+a'(x)\ge a(x).

The decrease in auxiliary failure probability thus pays for the increase in offline credit and leaves a contribution toward the online vertex’s dual variable.

If w>wiw > w_i, set a(x)=ν(I+x(P−I))mha(x)=\nu(I+x(P-I))^m h. There is no coverage gain, although the age distribution still changes. The same recurrence shows that k=(I−m(P−I))hk=(I-m(P-I))h is nonnegative and has stationary expectation γ\gamma. Every state ν\nu reached by the algorithm satisfies 0≤ν≤π0 \le\nu\le\pi. Since k≥0k \ge0, we have νk≤πk=γ\nu k \le\pi k = \gamma. Together with credit monotonicity, this gives

−a′(x)≤γ−a(x).-a'(x)\le\gamma-a(x).

After integration, the credit created when w>wiw > w_i is at most the sampling probability times its post-arrival credit. This term is subtracted in the sampling deficit below. The accounting therefore includes state changes above the current edge weight, where no matching gain is available.

Water filling. Integrate the threshold credits to obtain one offline dual variable αi\alpha_i per vertex, and integrate one minus the auxiliary miss probability to obtain its contribution Pi\mathcal{P}_i to the surrogate primal objective. This objective lower-bounds the expected matching value. For an edge of weight wiw_i and sampling probability xx, the two update inequalities combine into

ΔPi−Δαi≥x(γwi−αi[x]).\Delta\mathcal{P}_i-\Delta\alpha_i \ge x(\gamma w_i-\alpha_i[x]).

where αi[x]\alpha_i[x] is the credit after the hypothetical update. This suggests the terminal deficit di(x)=γwi−αi[x]d_i(x)=\gamma w_i-\alpha_i[x]. These deficits are continuous and nonincreasing. A large deficit means that the edge’s dual constraint still requires a large contribution from the arriving vertex. The algorithm increases the coordinates with the largest deficit until their total is one; a zero-weight dummy absorbs any remaining probability. Every used coordinate has the same terminal deficit β\beta. This gives dual feasibility, while integrating the two update inequalities pays for ∑iΔαi+β\sum_i \Delta\alpha_i+\beta. Summing over arrivals proves the competitive guarantee γ\gamma.

Tournament feasibility. The remaining condition belongs to the selection process. For each 1≤r<m1 \le r < m, let Vr=∏k=1r(1−Xk)V_r=\prod_{k=1}^{r}(1-X_k). The tournament exists when

E[(s−Vr)+]≤Hr(s):=s−m−rm+m−rm(1−s)m/(m−r)(0≤s≤1).\mathbb{E}[(s-V_r)+] \le H_r(s) := s-\frac{m-r}{m}+\frac{m-r}{m}(1-s)^{m/(m-r)} \qquad(0 \le s \le1).

The singleton condition follows from the quantile construction. For repeated candidates, condition on the first reset. The remainder starts at age zero and has bounded age. Its minimum and mean failure products satisfy short recurrences. Replacing this fresh product by a two-point distribution with the same mean, supported at its lower and upper bounds, increases every convex positive-part expectation. This avoids enumerating the reset patterns.

The initial age is unbounded. Conditional Jensen combines its older quantile bins into an explicit integral, while the pooled ages remain one point mass. Conditioning on the first reset thus gives a convex upper bound with at most 2r2r age-averaged terms and a point mass for the no-reset case. A quadratic estimate handles thresholds near zero. Elsewhere, chords between certified endpoint values bound the curve. Minimizing the gap between each chord and HrH_r reduces its validity to an exact integer-power inequality. A finite rational partition therefore covers every real threshold; Appendix § 9 gives the construction.

Choosing the win map

For fixed mm and pp, the necessary singleton constraint is W(Y)⪯icxUm−1W(Y) \preceq_{\mathrm{icx}} U^{m-1}, where YY is an output of the stationary reset process, UU is uniform on [0,1][0,1], and ⪯icx\preceq_{\mathrm{icx}} denotes increasing convex order. To see why pooling arises, fix a baseline b∈[qm−1/m,1/m]b \in[q^{m-1}/m,1/m] and consider maps of mean 1/m1/m. Their integrated lower-quantile curve S(u)S(u) must satisfy S(u)≥buS(u) \ge bu and S(u)≥um/mS(u) \ge u^m/m. The smallest permitted values at the seed’s quantile-bin endpoints are therefore given by

ϕb(u)=max⁡{bu,um/m}.\phi_b(u)=\max\{bu,u^m/m\}.

The successive secant slopes define a nondecreasing win map. The linear part assigns a common score to the youngest ages, and the remaining slopes preserve the older quantile-bin scores. A renewal formula shows that, at fixed baseline, γ(W)\gamma(W) is nondecreasing in the stationary upper-tail score sums. The pooled map maximizes these sums at fixed baseline. Theorem 6 proves this comparison, including maps whose mean is less than 1/m1/m, and reduces the optimization to the choice of bb.

Age also suffices for a broader class of processes with independent resets. Conditional on the reset times, each cycle contributes at most one nonconstant factor to a failure product. Replacing its terminal score by its conditional mean preserves avoidance probabilities and, by Jensen’s inequality, preserves the tournament constraints. Proposition 9 proves this reduction by averaging over the internal randomness between resets. The subsequent pooled replacement optimizes only the singleton relaxation; its higher-multiplicity constraints still require the certificate described above.

Correlated Selection and Weight Thresholds

The stationary geometric-age seed

Fix m≥2m \ge2, a reset probability p∈(0,1)p \in(0,1), and q=1−pq = 1-p. Start Z1Z_1 with distribution π(z)=pqz\pi(z) = pq^z, z≥0z \ge0. At exposure kk, independently draw a reset bit BkB_k with probability pp of being one. If Bk=1B_k = 1, output Yk=ZkY_k = Z_k and set Zk+1=0Z_{k+1} = 0. Otherwise output Yk=−1Y_k = -1 and set Zk+1=Zk+1Z_{k+1} = Z_k + 1. Every offline vertex gets an independent seed.

References

  1. [1][AGKM11] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253–1264. SIAM, 2011.
  2. [2]Guy Blanc and Moses Charikar. Multiway online correlated selection. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1277–1284. IEEE, 2022. Full version: arXiv:2106.05579v2, 2021.arxiv.org/abs/2106.05579
  3. [3]Moses Charikar, Monika Henzinger, and Huy L. Nguyen. Online bipartite matching with decomposable weights. In Algorithms—ESA 2014, volume 8737 of Lecture Notes in Computer Science, pages 260–271. Springer, 2014.arxiv.org/abs/1409.2139
  4. [4]Nikhil R. Devanur, Zhiyi Huang, Nitish Korula, Vahab S. Mirrokni, and Qiqi Yan. Whole-page optimization and submodular welfare maximization with online bidders. ACM Transactions on Economics and Computation, 4(3):14:1–14:20, 2016.
  5. [5]Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 101–107. SIAM, 2013.
  6. [6]Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge-weighted online bipartite matching. Journal of the ACM, 69(6):45:1–45:35, 2022. Conference version in FOCS 2020.
  7. [7]Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In Internet and Network Economics: 5th International Workshop, WINE 2009, volume 5929 of Lecture Notes in Computer Science, pages 374–385. Springer, 2009.DOI
  8. [9]Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online matching: A brief survey. ACM SIGecom Exchanges, 22(1):135–158, 2024.arxiv.org/abs/2407.05381
  9. [10]Fredrik Johansson. Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8):1281–1292, 2017.arxiv.org/abs/1611.02831
  10. [11]Thomas Kesselheim, Marco Molinaro, Kalen Patton, and Sahil Singla. Online algorithms via minimax and posterior matching. https://arxiv.org/abs/2608.01616, 2026. To appear in FOCS 2026.
  11. [12]Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1216–1225. SIAM, 2013.
  12. [13]Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 352–358. ACM, 1990.DOI
  13. [14]Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013.DOI
  14. [15]Alfred Müller and Ludger Rüschendorf. On the optimal stopping values induced by general dependence structures. Journal of Applied Probability, 38(3):672–684, 2001.DOI

Paper details

vlnc:W_pmubtc9m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents