Learning-Augmented Online Bipartite Fractional Matching
Authors: Davin Choo
Billy Jin
Yongho Shin
Venue: NeurIPS 2025 poster ()
Keywords: Learning-augmented algorithms
algorithms with predictions
algorithms with advice
robustness-consistency tradeoff
online bipartite matching
AdWords
online algorithms
Primary area: theory
TL;DR: We develop learning-augmented algorithms for vertex-weighted and unweighted online bipartite fractional matching, with application to AdWords, and establish new robustness-consistency tradeoffs.

Abstract: Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive ``coin flip'' strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.

Learning-Augmented Online Bipartite Fractional Matching
Davin Choo +
Harvard John A. Paulson School Of Engineering And Applied Sciences
Harvard University
Boston, Massachusetts, USA
davinchoo@seas harvard. edu
Billy Jin 18
Yongho Shin
Daniels School of Business
Institute of Computer Science University of Wroelaw Wroclaw, Poland yongholcs uni wroc. pl
Purdue University
West Lafayette, Indiana, USA jin6080purdue. edu
Abstract
Online bipartite matching is a fundamental problem in online optimization, ex- tensively studied both integral and fractional forms due its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning augmeeted algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching each iteration. develop algorithms for both the weighe-wegghted and unweighted variants that provably dominate the naïve "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, AdWords problem under the small bids assumption, yielding significant improve- ment over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the bobustness-consisernn tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.
algorithm for the vertex weeethee setting extends to the
1 Introduction
Online bipartite matching a fundamental problem online optimization with significant applica- tions in areas such online advertising [MSVV07, FKM+09), resource allocation [DISW19], and ride-sharing platforms [DSSX21, FNS24]. its classical formulation [KVV90, AGKM11) 1], the input a bipartite graph where one side of (possibly weighted) offline vertices is known in advance, while the other side of online vertices arrives sequentially one at time. When an online vertex arrives, its incident edges are revealed, and the algorithm irrevocably decides whether to match and, if so, to which currently unmatched neighbor. The objective is to maximize the total weight of the matched offline vertices. Algorithms for online bipartite matching are often evaluated by their competitive ratio: An algorithm is p p-competitive if it always outputs a matching whose (expected) total weight is
Part of work done while the author affiliated with the National University of Singapore, Singapore. Work done while the author was at the University of Chicago Booth School of Business, USA. 1 Part of work done while the author was affiliated with Yonsei University, South Korea.
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

at least p times the weight of the best matching in hindsight. In seminal paper, [KVV90] proposed the RANKING algorithm and showed it is (1 - competiive for the unweighted setting. This competitive ratio is best-possible, and was later extended to the vertex-weighted case by [AGKM11].
Online bipartite matching has also been studied in the fractional setting, where edges can be fraction- ally chosen, provided that the total fractional value on the edges incident to any vertex does not exceed one [WW15, HPT 19, HTWZ20, HHIS244. Fractional matching is important both theoretically and practically. It naturally models settings where online arrivals are divisible or offline vertices have large capacities [KPO0, MSVV07, BJN07, FKM 09, MNS 12, DHK 16, FN24], and it forms the basis for designing integral algorithms using rounding techniques [FSZ16, BNW23, NSW25]. For fractional vertex- weeihhed online bipartite matching, the BALANCE algorithm of [BJNO7] gets a competitive ratio of (1 1/e), which is best- best-possible and matches the ratio in the integral case.
The main challenge in online bipartite matching is that irrevocable decisions must be made with- out knowledge of future arrivals. Uncertainty in the arrival sequence is typically modeled either adversarially or stochastically. The adversarial model assumes no structure and measures worst-case performance, but can be overly pessimistic. On the other hand, the stochastic model assumes arrivals are drawn from known distribution [FMMM09], but such distributions are often estimated and may be inaccurate. These models thus represent two extremes, each with practical limitations. A middle ground is offered by algorithms with predictions, or learning- auginnnted algorithmss [MNS12, LV21], which incorporates advice - derived from data, forecasts, or experts - of unknown quality. The perfor- mance typically measured in terms of its robustness (guaranteed performance regardless of advice quality) and consistency (performance when advice is accurate) [LV21, KPS18) 18). In online bipartite matching, an algorithm r-robust its competitive ratio is at least r. and c-consistent it achieves at least a c-fraction of the total weight from following the advice (see Definition 4). A natural baseline is the COINFLIP algorithm, which randomly chooses between robustness- and consistency-optimal strategies. For matching, its tradeoff curve is the line segment between (1 - (1,1/e, - 1/e) and (0, 1) in the weight- case, or (1/2, 1) in the unweighted case [JM22].
This paper investigates the Bammigg-augmentn framework, building on prior work including [MNS07. MNS 12, AC122, JM22, SE23, CGLB24]. Particularly relevant are the works of Mahdian et al. [MNS07, MNS12] and Spach and Ene [SE23]. Mahdian et al. studied the AdWords problem (introduced in [MSVV07]), with advice in the form of a recommendation assigning each online impression to specific offline advertiser. They proposed a learning- -ugmmente algorithm under the small bids assumption that outperforms the naive COINFLIP strategy, but only over part of the robustness range. Meanwhile, [SE23] generalized this result to Display Ads and the generalized assignment problem [FKM+09], However, as shown in Fig. 1, neither of these algorithms dominate COINFLIP across the full robustness spectrum. This raises a natural question: Does there exist a
tradeoff of online bipartite matching under the
algorithm for online bipartite matching that dominates COINFLIP across the entire range of robustness?
1.1 Our contributions
We answer the above question affirmatively by presenting vertex certex-weighted and unweighted online bipartite fractional matching whose robustnexs-consistenny consistency tradeoff' Pareto-dominate that of COINFLIP across the entire range of robustness (see Fig. 1).
algorithms for both
Motivated by [MNS07, MNS12, SE23), we take the advice to be feasible fractional matching that is revealed in an online fashion: upon arrival of each online vertex v, the algorithm is given as advice fractional matching values for each neighboring edge of v. Moreover, as in IMNS07, MNS12, SE23], our algorithms are parameterized by a tradcoff parameter E [o, 1] that represents how closely we follow the advice. At the extremes, our algorithms blindly follow the advice when > = 1 and revert to BALANCE when >= = 0.
For the vertex- weighted setting, we present an algorithm LEARNINGAUUGMENNEDDBAAANCC (LAB) with the following guarantees:
Theorem 1. For any tradeoff parameter À E [0, 1], LEANNINGUUGMEENTDDAAAAA robust and (XX-cconsisten) algorithm for wertex- online bipartite fractional matching, where
is an r(A)-
r(A) := 1 1- - - X) In(1 Xe - x(1-) and c(>)= ;= 1 -
'A third property, smoothness, requires graceful degradation with advice quality [EADL24]. See Section 2.

---

Consistencs
Consistency
0.73
0.73
0.63
0.63
0.63
0.5
0.63
Robustness r
Robustness r
LAB (Sect 3)
CLIPFLIP
PAW (Seet 4)
Ou: UB (Sect 5)
[MNSUT, MNS12]
Our UH (Seet 5)
LAB (Sect
UB of [JM22, CGLB21
[SE25]
UB of [JM22]
COINFLIP
(a) Verthx-weighted setting and AdWords under
(b) Unweighted setting
small bids assumption
Figure I: Robustness- tradeoffs of previous works and our results.
This algorithm is based on BALANCE where the penalty function is modified to udvice-dependerd To analyze this algorithm, we adopt the standard primal-dual analysis of online bipartite matching and first prove its performance when the advice is integral. We then prove that the robustness and consistency minimized when the advice is integral, yielding the same guarantees for the general fractional advice case.
We further show that LAB extends to the AdWords problem under the small bids assumption, yiclding a significant improvement over [MNS07, MNS12].
Theorem 2. Consider the small bids assumption where the maximum bid-to- toddge- ratio is bounded by some sufficiently small >> 0. For any tradeoff parameter E [0, there exists an r(x) / In(1/e)) and c(A) (1 - (nLe)))(())))oomm -consistent algorithm for AdWords with advice, where r rA) and c(A) are the same in Theorem
To achieve this result, we first extend LAB to the fractional AdWords setting while preserving its robustness and consistency, and then employ reduction from [FN24] to reduce the integral AdWords problem to the fractional problem with small loss under the small bids assumption.
Observe in Fig. that the aubustness-consitte COINFLIP in the unweighted setting: the top-left endpoint of the tradeoff for LAB is (r,c) = (0. 1), whereas in the unweighted setting COTNFI.IP can be implemented to be 1 1/2-robust even when This happens because any maximal matching in an unweighted graph is automatically 3 |-robust. To beat COINFLIP in the unweighted setting, tighter analysis of L.A would be required but this proved difficult using our current analysis framework for LAB, even when the advice is integral. Instead, present another algorithm called PUSHANDWATERFFL (PAW) for the unweighted setting with integral advice that circumvents the aforementioned challenge the analysis.
tradeoff of LAB lies below the linear tradeoff of
1.
Theorem 3. For any tradeoff parameter À E [0, 1}. PUSHANDWATERELLL is r(A)-robust and c(A)-consistent for unweighted online bipartite fractional matching with integral advice, where
r()) = 1- (1 x x2/2) A and c(A) = 1 (1 A
PAW based on the unweighted version of BALANCE, also known as WATERFILLING, with one additional step each iteration where first increases the fractional value of the currently advised edge until the "level" of the advised offline vertex reaches the tradeoff parameter X. We analyze PAW using primal-dual but with different construction of dual variables from LAB.
We complement our algorithmic results by presenting an upper bound on the robustness-cossisennyy tradeoff of any learning-augenn augmented algorithm for the unweighted setting with integral advice in

---

Section 5, improving upon the previous upper bound results [JM22, CGLB24] (see Fig. 1). Note that this result implies the same impossibility for more general problems including the vertex- weighted setting and the AdWords problem. To obtain our hardness result, we construct two adaptive adversaries - one for robustness and the other for consistency. The construction of these adversaries is inspired by the standard upper-triangular worst-case instances [KVV90], while we modify this construction to make the two adversaries have the same behavior until the first half of the online vertices are revealed. Due to this modification, the two adversaries are indistinguishable until the halfway point of the execution while inheriting the difficulty from the standard worst-case instances. We then identify set of conditions characterizing the behavior of Pareto-optimal algorithms on our hardness instance and solve a factor-revealing LP to upper bound the best possible consistency subject to the constraint on the robustness to be r, for each r E [1/2, 1 1/e].
Lastly, we implemented and evaluated our proposed algorithms I.AB and PAW in Section 6 against advice-free baselines on synthetic and real-world graph instances, for varying advice quality parame- terized by a noise parameter 7 where larger y indicates poorer advice quality. As predicted by our analysis, the attained competitive ratios of both LAB and PAW begin at I under perfect advice and smoothly degrades as the Y increases. Unsurprisingly, for sufficiently large y, the worst case optimal advice-free algorithm BALANCE outperforms both LAB and PAW.
Full proofs, further related work, and code are provided in the supplementary material. Environment numberings are made to be consistent with the full version, but may not appear sequentially here.
2 Preliminaries
Online bipartite matching. In the vertex-weighted online bipartite fractional matching problem, we have a bipartite graph G = (U U E) and weight w,, 2 0 for each u E U. If w,, = 1 for every E U, then the problem is called unweighted. The vertices in U are the offine vertices, and their weights are known to the algorithm from the very beginning. On the other hand, the vertices in V are the online vertices, and arrive one by one. Whenever v E V arrives, its neighborhood (C) == {u E U (u, v) E E'} is revealed. Since the online vertices arrive sequentially, we use the notation < v to mean that t arrives earlier than v. Similarly, for each offline vertex u U, we also use (u) := {o E V (u, E }} to denote the neighborhood of u.
We use the analogy of waterfilling describe the behavior of the algorithm. When V arrives and its neighborhood (u) is revealed, the algorithm decides at that moment the amount Tupy of water to send from e to each (v) subject the constraints that:
the total amount of water supplied from v does not exceed 1, i.e. EmEN(t) Tuy S 1;
* each offline vertex u E U can hold at most unit of water, i.e., EieN(w)atg Tu,s S 1.
This decision is irrevocable, meaning that, { (w))())) cannot be modified in the subsequent iterations. Let E _& be the final solution of the algorithm. Note that x is fractional matching in the hindsight graph G. The weight of this solution is defined to be L(u,)een W.Tunw The objective of this problem is to maximize the weight of the solution.
Advice. Each online vertex v E V arrives with a suggested allocation {au, Sau.rhueNoo N()), where we assume {uu,, (u,v) E E} E E is a feasible fractional matching in the hindsight graph G.
Performance measures. Denote the value of the final output of an algorithm by ALG, the value of an optimal solution in the hindsight instance by OPT, and the value obtained by the advice by ADVICE. We can then formally define the robustness and consistency of a learning- sorming-augmented algorithm.
Definition 4 (Robustness and Consistency). For some r E [0, 1], we say an algorithm is r-robust if E|ALG] 2 r OPT for any instance of the problem. On the other hand, for some e [0. 1]. we say an algorithm is c-consistent if [| 2 c ADVICE for any instance of the problem.
Notice that, when we define the error of the advice to be 7 == ADVICE/OPT [0. 1]. the consistency implies the smoothness of the algorithm since we have E[ALG] 2 c7 OPT.
Primal-dual analysis. To prove the robustness and consistency of our algorithms, we adopt the standard primal-dual analysis for online bipartite matching [DJK13]. Observe that, for vertex- weighted bipartite matching, the primal and dual LPs are formulated as follows:

---

max E(U,)EE WaFaa
min EvEu Ou + =VVEV Bo
s.t. EveN(u) Fuo 1,,
E U,
02 + 3r Wui
v(u, v) E E,
EneN(e) Buo S 1, uup 0,
E
0u 2 0,
Vu E U,
B. 2 0,
Yu V.
V(u, E E;
The following lemma is the cornerstone of the primal-dual analysis. Lemma 5 (see, e.g., [DJK13, FHTZ22J). Let a E R4 be a fractional matching output by an
algorithm. For some E [0, 1}, if there exists (a. 3) E R4 x R satisfying
(reverse weak duality) Σ E(,,)EE WaFnn, Eneu On Evev By and
(approximate dual feasibility) a. + 3, 2 w. for every (u,v) E,
we have ALG 2 p PPOPT.
3
Verthx-weighted matching with advice
We now present our algorithm BLARNINGAUGMENTEDEEE bipartite matching with advice and provide proof sketch showing that achieves the robustness- consistency tradeoff stated in Theorem 1. Detailed pseudocode is given in Appendix A and a full analysis provided in the supplementary material.
(LAB) for vertex-weighted online
Algorithm description. Given a tradeoff parameter À E [0, 1}. we define fo : [0, 1] + [0, 1] and fi [0, 1] [0, as follows, where W is the Lambert W function:
if E Ae [0,
fo(=) == minfe ,1,, and f1(2) =
if E [Ae pol-x,1)
(I)
W
if 1,
Based on these functions, we define f: [0, 1]2 + [0, such that
f(A, (X),
if X, iA
(2)
For clarity, let us describe LAB as continuous process. Upon the arrival of each online vertex v E V along with the advice {au,u) define A,, := >.E LiEN(w) Gu,t as the total advice-allocated amount to each offline vertex u E (v),, up to and including v. LAB then continuously pushes an infinitesimal unit of flow from v to the neighbor X, is the total amount allocated to u by the algorithm right before it starts pushing this infinitesimal unit of flow. This continues until v is fully matched (i.e. one unit of flow pushed) all neighbors are saturated.
NN)) maximizing w. f(A, X.)).. where
First, we give intuition for the algorithm. For online vertex and an offline neighbor u E N()), the amount allocated from v to u should depend on three factors. Firstly, a higher w. should lead to larger Fu,r- Secondly, the more is filled, the less desirable it is allocate to it further, preserving capacity for future vertices. Thirdly, vertices favored by the advice should receive more allocation.
The classical BALANCE algorithm handles the first two factors by choosing the offline vertex with the highest potential value w., (1 - g(X.)) via a convex increasing penalty function g(2) = e= To incorporate the third factor, LAB introduces depends on the total advice allocation A; see Fig. 2. This function is increasing in X (penalizing already-fill filled vertices) and decreasing in A (lower penalty for vertices recommended by the advice), thereby encouraging alignment with the advice.
advice-aware penalty function f(A, X) that also
The penalty function f used by our algorithm is defined in Eq. (2) based on the functions fo and Si from Eq. (1). While fo and f1 are derived from the primal-dual analysis, and their exact forms are not crucial for intuition, the structure of of admits a natural interpretation. Intuitively, if an offline vertex
5

---

has received less allocation than the advice suggests (i.e., A, > Xw). then the penalty function treats u as if it were already saturated under the advice. Conversely, if u has been filled beyond the advised amount (i.e., A, I X,). then the penalty effectively treats the excess allocation X. Aa as it were added despite the advice indicating u should unmatched.
08
0.5
0.5
006
0.6
100
160.000
0.0
46..
169.
0.2
0.2
0.2
0.0
0.0
0.2
0.1
04
05
0.0
0.1
05
0.0
0.4
0.6
0.
(8) fu. f1 with À = 0.1
(b) fu. f1 with = 0.3
(c) fo- f1 with À = 0.5
1.0
-00
1.2
0.6
0.0
0.5
0..
0.4
0.5
02
0.0
08
0.0
(d) f with X = 0.1
(e) f with À 0.3
(1) f with A 0.5
Figure 2: for fí, and f with À E {0.1, 0.5, (a)-(c) depict the function values fo and fi with respect to z E [0, 1]. (f)-(f) depict the contour plots with respect to A E [0, 1] and X E [0, 1]: the brighter the color is, the closer to the function value is.
Sketch of analysis. We use the primal-dual framework (Lemma 5). We initialize all dual variables to O. When online vertex u V arrives, let A be the amount allocated by the advice up to and including v. Similarly, let x(")) be the amount allocated to u by the algorithm up to and including v. Let uu,v be the amount allocated by the algorithm in this iteration.
Then, we update the dual variables as follows:
Cu + Ou Fa,v ff (w) xx(") for every u E N(v,, and
* 3 t- max.eN()) (w. - ,(A(),x(')))
For the reverse weak duality, the following lemma follows directly from this construction: Lemma 9. The value of the algorithm is equal to the objective value of (a, B) in the dual LP.
Note that the dual variable 3, defiend to be the value of the highest potential neighbor after has sent its allocation while the dual variables O, are updated so to satisfy Lemma 9.
We now argue the approximate dual feasibility. As first step, consider the special where the advice is integral. In this case, we can simplify the robustness and consistency expressions by noting that A(()) E {0, } for all E U and V.
Lemma 12. When advice is integral, the algorithm r-robust and c-consistent where
+ (1- {T00 fo(z)dz (1 (of(()))), 1/¹ f1 (-(())))) Xe(0.11
r min min
-Y. 11() + 011++1110000 +1-11001) m(00n (/"" So(=)d= + (X- 8).
c= min min
x | YE(

---

In addition, the expressions on the RHS above evaluate to exactly r(X) and c(X) in Theorem 1, respectively.
To complete the analysis, one can show that robustness and consistency remain unchanged even for the more general fractional advice setting: robustness is determined entirely by fi, while consistency follows from reducing any fractional instance to an equivalent integral case.
Remark. By tweaking the above analysis and using the reduction technique of [FN24], we can obtain an algorithm for AdWords under the small bids assumption with guarantees given in Theorem 2. For the details, see the supplementary material.
4 Unweighted matching with integral advice
In this section, we introduce and analyze a new algorithm tailored to the unweighted setting with integral advice, which we call PUSHANDWATEREEN algorithm, it is worth noting that our theoretical guarantees of LAB are dominated by COINFLIP in the unweighted setting; see Fig. 1. This suggests that our previous analysis is not tight for unweighted instances. However, since that analysis was independent of the vertex weights, we find it challenging to improve for the unweighted setting, even when we are given integral advice. As such, we propose PAW for the setting of unweighted matching with integral advice. In the following, we assume the advice is integral and represent it as a function A : V + U {1}, where A(v) is the advised match for V. and A(v) I indicates that is advised to remain unmatched. Detailed pscudocode is given in Appendix A and a full analysis is provided in the supplementary material.
(PAW). To motivate why we need new
Algorithm description. As before, we describe PAW as a continuous-time process. Define the level of an offline vertex u E U as the total amount of water it has received so far. Upon arrival of online u E V, with neighborhood (1) and advice A(v), the algorithm proceeds in two phases:
Phase (Push): Push flow into A(v) until its level reaches A. Phase (Waterfill): Distribute any remaining flow from across (D) via the standard waterfilling.
Sketch of analysis. As in the analysis of LAB, we use primal-dua framework to characterize the robustness and consistency of PAW. The dual variable construction differs from the vertex- -riiht-ee
case and relies on continuous and non- non-decreasing function g [0, 1] + [0. 1] such that g( = 1. We call such a function a splitting function.
The dual variables (a,, 33 are initialized to zero, and are updated as follows. When an online vertex u sends an infinitesimal amount dz of flow to a neighbor dz into ((d) dz and (1 - g(dw)) dz. Then, we increase o,, by g(d,) dz and B, by (1 - g(d,)) dz.
(v) whose current level is d, split this
Since g(d,) E [0, 1], both and 3 remain nonnegative. Moreover, by construction, the reverse weak duality in Lemma 5 holds with equality: every infinitesimal unit of flow is split exactly into two values contributing
au and 3g, respectively. Thus, to analyze the robustness and consistency of PAW, it suffices to identify splitting functions g such that the resulting (a. B) is approximately dual feasible, maximizing the respective performance parameter p in Lemma 5. To this end, we identify the following two splitting functions Jr and gc, tailored for robustness and consistency, respectively:
(2) == (1+1 A),
Vz E [0, A),
V2 E (), V> E [1.
and 96(2)
Vz E [
These functions lead to the robustness and consistency bounds in Theorem 3.
5 Upper bound on robustness-consistenyy tradeoff
In this section, we present an upper bound result for the unweighted setting with integral advice. We define two adversaries, R and C, which target robustness and consistency, respectively, against any fractional matching algorithm M. For a given positive integer ni, both adversaries construct a bipartite instance with set U of 2n offline vertices and a set V of 2n online vertices. See Fig. 6 for an illustration of the upper bound instance. Detailed pseudocodes of these adversaries and full analysis are provided in the supplementary material.
7

---

Common Phase
16
Robustness Phase
43
03g
16
04.4
14
215
15
Consistency Phase
1G
Figure 6: An illustration of the hardness construction. The instance begins with the common phase, which is the same in both adversaries. After the common phase, the instance proceed in of two ways, designed to be hard for robustness or consistency, respectively.
The two adversaries behave identically during the first iterations, follows: In the first iteration 1), they present the first online vertex in to M, with vi connected offline vertices U. The advice A(v1) ) is chosen arbitrarily. For each subsequent iteration É 2,..., the adversary presents online vertex 12 which adjacent the neighbors (v; of the previous vertex f4-1> excluding two vertices: the previous advice A(v--1) and the offline vertex that has been filled the least so far by M.
Starting from iteration t = 1, the behaviors of the two adversaries diverge. The robustness adversary R continues on the vertices advised be matched so far in the classical setting online fractional bipartite matching without advice: each online vertex is adjacent to the same neighbors as the preceding one, except for the offline vertex that has been filled the least so far by M. In contrast, the consistency adversary C simply presents matching to the offline vertices that were advised to be unmatched in the first n iterations, allowing the algorithm to fully saturate them.
We formulate a factor-revealing LP that upper bounds the consistency ratio of any algorithm M against C while ensuring the algorithm r-robust against R, for any E [//2, 1 1/e]. To this end, we assume that M satisfies the following conditions: MM saturates each online vertex unless its neighbors are all saturated and, in the common phase, M pushes the same amount to the neighbors except the advised offline vertex at each iteration. We prove these conditions are without loss of generality. The LP is formulated follows:
maximize C
a 3
subject to 2t + (2n + 1) J4 S
1 (. (1, 34
(
d Σ1- T It, de = E T
11. 1 3
d. S dr+1,
11 11 3 1
E Mir $1,
110 (....... 71 3 1A (1) (1, 34
d = d; + Dt 2s=1 Vi.e1
d0 < i+11
a We
(t....,, E 14 (u (.......
1}.
Et_ (d, + d,) + Ete Ei Wi. 2nr,
Σ de + 2nc.
0 S 34, Ft, dr. de, Vitt (1) <
vt E (1,...,,n) Vi ft,....................... (t.
Experiments
We experimented on synthetic random graphs and real-world graphs. Fach plot is generated by letting each algorithm solve 10 instances for different noise parameter values. Source code implementations and experimental scripts are given in the supplementary material.

---

6.1 Graph instances
We experimented on two families of synthetic graphs - Rédós-Rényi (ER) and Upper Triangular (UT), and 6 real-world graphs from the Network Data Repository [RA15]. For n E {100, 200, 300) and edge probability p E 0.2,, 0.5}, ER(n, p) graphs are generated with n offline and a online vertices, with each possible bipartite edge existing independently with probability p. For E {100, 200, 300}, each UT(n) graph consists of n offline vertices and n online vertices, where the i-th online vertex is connected to the last i + offline vertices. Meanwhile, we pre-process real-world graphs in a similar manner to [BKP20] to obtain random bipartite graphs: first, shuffle all vertices indices in the real-world graph, take the first |n/2] as the offline vertices and the next |n/2] as online vertices and only keep the bipartite crossing edges. For weighted instances, each offline vertex is given random weight between 0 and 1000.
6.2 Advice generation
For each graph G with n vertices and given noise parameter Y E [0, 1]. we generate noisy prediction G. of G follows: each online vertex v retains random (1 1--- 7) fraction of its true neighbors and gains a random y fraction of its non-neighbors. Thus, when y = 0, the prediction is exact (Go - 9) and when y = 1, it corresponds to the complement graph (C) = G)
To generate the advice for the t-th arriving online vertex (for t [rz)), we solve linear program that maximizes the (weighted) matching objective. This is done subject to two components: the actual decisions made for the first t 1 arrivals in the true graph G, and noisy prediction of the future arrivals from time + 1 n, based on Gyy. Importantly, the current arrival at time not included in the noisy future but is instead the decision variable of interest. In more detail, the advice at time t is generated by perturbing the true future subgraph (i.e., the part of 9 involving vertices + 1 to n) to create noisy forecast. We then solve for the optimal decision at time that maximizes the matching the
value, given the past decisions up to 1 (in G) and the predicted future (in Gy). Since true graph up to and including time t, this process ensures that the advice at each time step is always feasible and based valid optimization problem over a fully specified nevertex instance.
6.3 Benchmarked algorithms
The two baselines are GREEDY and BALANCE. The former greedily matches the online vertex with its highest weighted available offline neighbor while the latter fractionally matches based on the penalty function g(z) = exp(= - 1). In the unweighted setting, BALANCE is equivalent to the classic WATERFILLING algorithm. Note that both GREEDY and BALANCE are independent of any predictions, so they achieve constant performance for any noise parameter y [0. 1]. We also implemented and benchmarked our LAB and PAW algorithms, which take as inputs XLAB and λxAw respectively. Note that we only run PAW for unweighted instances. Recall from Theorems 1 and 3 that L.B and PAW have different consistency values with respect to their parameters: the consistency of L.A is 1 + ÂLAB exp(>LAR - 1) while the consistency of PAW is 1 (1 APAW) exp(Apxn - 1). To compare between them at the same consistency value, we set APAw = 1 + W (ALAB exp (ALAB 1)). Since B BALANCE already achieves competitive ratio of - 1/e ~ 0.632, we consider consistency ratios of {0.7, 0.8, 0.9, 1.0} when running LAB and PAW. For consistency ratio of 0.7, we set ALAB R 0.11 and ΛpAW R 0.51. For consistency ratio of 0.8, we set ÀLAB R 0.29 and λPAw ~ 0.74. For consistency ratio of 0.9, we set dLAB Ro 0.52 and wPAw z 0.89. For consistency ratio of 1.0, we set ÀLAB = 1 and XPAw 1.
6.4 Qualitative takeaways
Fig.7 7 illustrates a subset of our empirical results. As predicted by our analysis, the competitive ratio attained by both LAB and PAW degrades as the noise parameter y increases. In particular, when = 0 (i.e., perfect advice), both LAB and PAW achieve a competitive ratio of I when ÀLAB ApAw 1. As Y grows large, the advice becomes increasingly uninformative, and is unsurprising that the advice-free algorithm BALANCC. eventually outperforms both learning- augmented algorithms, with the crossing point depending on the underlying graph instance.
Such a pre-processing step is necessary because these real-world graphs not bipartite to begin with.

---

Greedy
LAB (A 0.11)
LAB (A 0.52)
PAW D - 0.51)
PAW (A 0.89)
0.29)
1.00)
0.74)
1.00)
ER(300,0.2)
UT(3300
Nocfb-CaltechSS
econ-beaure
Obtained competitive ratio (Mean of 10 runs 5.d.)
6.00
0.04
Unweighted instances
030
0.6
0.4
8.20
047
0.5
4.8
ER(300,0.2)
UT(3000
socfb-Caltech36
econ-beause
1.30
1.20
146
Weighted Iwsteeennnttttnnn Instainces
1.8
047
0A5
042
040
0.9
0.00
035
62
64
66
18
64
66
08
96
Noise parameter Y
Figure 7: Subset of empirical results: ER(300, 0.2), UT(300), and 2 real-world graphs (socfb- Caltech36, econ-beause). See the supplementary material for our full set of experiments.
Interestingly, across all our experiments - including those in the appendix - we consistently observe phenomenon where there appears to exist critical noise level y such that the competitive ratios of all runs of LAB and PAW (across different À values) converge and coincide with that BALANCE. This suggests that y", the advice becomes effectively uncorrelated with the input, causing the behavior of LAB and PAW to resemble that of BALANCE regardless of the weighting parameter A. While do not currently have theoretical explanation for this convergence, it is compelling empirical observation that may point to deeper structure in the robustness conpeessssscssssssnnecce tradeoff and warrants further investigation in future work.
7 Conclusion and Open Problems
We studied the robustness-consistenn tradeoffs of learning- augmented algorithms for online bipartite fractional matching. We proposed and analyzed two algorithms, LAB and PAW, and established an improved hardness result.
In our current work, PAW relies on integral advice while LAB can accommodate fractional advice. While it is a natural question to ask if there can be a unified algorithm and analysis, our current analytical framework is unable do so. The analysis of LAB agnostic the weights, making unclear how to demonstrate improved tradeoff in the unweighted case. Meanwhile, the analysis of PAW crucially relies on the integrality of the advice, and we were unable obtain comparable bound in the fractional case. We do not rule out the possibility of unified analysis, and we view this as a compelling direction for future work. We do not rule out the possibility of a unified analysis and view this as intriguing direction for future work.
Besides unifying the two variants, there are serveral other natural open and interesting research directions. Firstly, it would be interesting to develop theoretical explanation for the crossing point phenomenon observed in our experiments; see the discussion Section 6.4. Another direction would be to close the gap between our algorithmic results and the impossibility bounds. Progress on this front could come from an analytic proof of the impossibility result, as well as tight analysis of LAB in the unweighted setting. Finally, it would be interesting to extend our framework to broader variants of online matching, including Display Ads, the generalized assignment problem [FKM+09, SE23], and the multi-stage setting [FN24].
10

---

Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: DSSG-PhD/2021-08-0113 This work was partly supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2021-1121 10688, Artificial Intelligence Innovation Hub). This work was partly supported by an IITP grant funded by the Korean Government (MSIT) (No. RS-2020-11201361 Artificial Intelligence Graduate School Program (Yonsei University)). Supported by NCN grant number 2020/39/B/ST6/011/
References
[AC122] Anders Aamand, Justin Chen, and Piotr Indyk. (Optimal) Online Bipartite Matching with Degree Information. Advances in Neural Information Processing Systems, 35:5724- 5737, 2022.
[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-sccond annual ACM-SIAM symposium on Discrete Algorithms, pages 1253- 1264. SIAM, 2011.
[BJNO7] Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253- 264. Springer, 2007.
[BKP20] Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorithmics (JEA), 25:1-37, 2020.
[BNW23] Niv Buchbinder, Joseph Naor, and David Waje. Lossless online rounding for online bipartite matching (despite its impossibility). In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2030-2068. SIAM, 2023.
[CGLB24] Davin Choo, Themis Gouleakis, Chun Kai Ling, and Arnab Bhattacharyya. Online bi- partite matching with imperfect advice. International Conference on Machine Leurning, 15:88722-871,, 2024.
[DHK 16] 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 (TEAC), 4(3):1-20, 2016.
[DJK13] Nikhil Devanur, Kamal Jain, and Robert Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourhh annual ACM-SIAM symposium on Discrete algorithms, pages 101-107. SIAM, 2013.
[DJSW19] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource alloca- tion problems. Journal of the ACM (JACM), 66(1):1-41, 2019.
[DSSX21] John P Dickerson, Karthik A Sankararaman, Aravind Srinivasan, and Pan Xu. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Transactions on Economics and Computation (TEAC), 9(3)1-17,, 2021.
[EADL24] Alex Elenter, Spyros Angelopoulos, Christoph Dürr, and Yanni Lefki. Overcoming brittleness in pareto-optimal learning augmented algorithms. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024.
[FHT722] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam, Edge- weighted online bipartite matching. Journal of the ACM, 69(6):1-35 2022.
11

---

[FKM 09] Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayuthan Muthukrishnan. and Martin Pál. Online ad assignment with free disposal. International workshop on internet and network economics, pages 374-385. Springer, 2009.
[FMMM09] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. Online stochastic matching: Beating 1-1/e. In 2009 50th Anmual IEEE Symposium on Founda- tions of Computer Science, pages 117-126. IEEE, 2009.
[FN24] Yiding Feng and Rad Niazadeh. Batching and optimal multistage bipartite allocations. Management Science, 2024.
[FNS24] Yiding Feng, Rad Niazadeh, and Amin Saberi. Two-stage stochastic matching and pricing with applications ride hailing. Operations Research, 72(4):1574-154: 2024.
[FSZ16] Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the twenty-seventh annual ACM-SIAM symposium Discrete algorithms, pages 1014-1033, SIAM, 2016.
[HHIS24] Hadi Hosseini, Zhiyi Huang. Ayumi Igarashi, and Nisarg Shah. Class faimness in online matching. Artificial Intelligence, 335:104177, 2024.
[HPT-19) 19] Zhiyi Huang, Binghui Peng. Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2875-2886 SIAM, 2019.
[HTWZ20] Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Fully online matching II: Beating ranking and water-filling. In 2020 IEEE 61st Annual Symposium Foundations of Computer Science (FOCS), pages 1380-1391, IEEE, 2020.
[JM22] Billy Jin and Will Ma. Online bipartite matching with advice: Tight robustness- consistency tradeoffs for the two-stage model. Advances in Neural Information Pro- cessing Systems, 35: 1555--14677 2022.
[KP00] Bala Kalyanasundaram and Kirk Pruhs An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):11-335, 2000.
[KPS18] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via MIL predictions. Advances Neural Information Processing Systems, 31, 2018
[KV990] Richard M Karp. Umesh Vazirani, and Vijay 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, 1990.
[LV21] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
[MNS07] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online adver- tisement space with unreliable estimates. In Proceedings of the 8th ACM conference on Electronic commerce, pages 288-294, 2007.
[MNS12] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM Transactions Algorithms (TALG), 8(1):1-29, 2012.
[MSVV07] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. AdWords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007.
[NSW25] Joseph Naor, Aravind Srinivasan, and David Waje. Online dependent rounding schemes for bipartite matchings, with applications. In Proceedings of the 2025 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 3116-3154, SIAM, 2025.
[RA15] Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI conference on artificial intelli- gence, pages 4292-4299 2015.
12

---

[SE23] Fabian Spach and Alina Ene. Online ad allocation with predictions. Advances in Neural Information Processing Systems, 36:17265-17295 2023.
[WW15] Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In International Colloquium on Automala, Languages, and Programming, pages 1070-1081. Springer, 2015.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the abstract and Section
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Justification:
In Section 7, discuss gap left open by algorithmic and impossibility results.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide proof sketches of our theoretical results in Sections to 5. Full analyses are given the supplementary material.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yss]
Justification: See Section 6. Source code implementations and experimental scripts are given in the supplementary materials.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide source code to experiments in the supplementary materials.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: See Section
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section and, in particular, Fig. 7. Full set of experimental results is given in the supplementary material.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [Yes]
14

---

Justification: We provide such information in the supplementary material.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: :
Answer: [Yes]
Justification: The paper conforms with the NuerIPS Code of Ethics.
Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The main contribution of this paper is investigating the theoretical aspects of online bipartite fractional matching under the -anning- framework.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cited the original owners in the paper and supplementary material.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: do not introduce new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
15

---

A Pseudocodes of our algorithms
Algorithm 1: Learning-Augmennte Balance Algorithm (LAB)
Input: Offline vertices U, tradeoff parameter [0,
Data: Online vertices V, edges E, and fractional advice E R
Output: Fractional matching æ E R
foreach E U do
X, 0
Amount allocated by algorithm I/ Amount allocated by advice
A +
foreach arrival of E V with neighbors (D) and advice (au.)uEN(() do
foreach E [v) do
Au f Au au,v
I/ Accumulate advice
Find the smallest e 2 such that EmEN(o) Zu,e S 1, where
Fu. = min(z E [0, Xu) wa (1 f(An, Xa + x)) s S
// e.g. via binary search
10
foreach E (v) do
Xa Xu + Fu.y
I/ Accumulate actual fractional matching
12
13
return 2
Algorithm 2: Push-and- Waterfill Algorithm (PAW)
Input: Offline vertices U, trade-off parameter [0.
Data: Online vertices V, edges E, and integral advice A : V + (0
Output: Fractional matching x E R
foreach E U do
di 0
Level of
foreach arrival of E V with neighbors (()) and advice A(v) do
(Phase 1): Push to advised neighbor A(v), up to max X d dA(u)} amount
((v) E (o)) then
T m0, dA(u)}
ZA(r). +
dA(w) + da(v) +
else
0 (Phase 2): Waterfill the remaining T Find the largest l such that EuEN(,) max (0, l dg) S
11
13
e min 1} foreach (c) do
15
Eu,v f Fu,v + max(0, E dut dn d, + ma, d..}
return 2
16


Reviews:
[{"review_id": "R7u5iySOZc", "reviewer": "Reviewer_ANVd", "summary": "This paper studies learning-augmented algorithms for online bipartite *fractional* matching, aiming to outperform the COINFLIP baseline by achieving better robustness–consistency tradeoffs.\n\nIn online bipartite matching, a bipartite graph is revealed incrementally: the offline vertices are known in advance, while online vertices arrive one by one, requiring irrevocable matching decisions to maximize the total matched weight. (In the vertex-weighted case, this means maximizing the sum of the offline vertex weights.)\n\nThe work focuses on a predictive setting where, upon each arrival, the algorithm receives advice suggesting a fractional matching. The algorithm seeks to remain robust to poor advice while exploiting accurate predictions.\n\nThe authors propose two algorithms: LAB for the weighted case and PAW for the unweighted case, and establish hardness results that delineate the limits of such tradeoffs.\n\n\nThe COINFLIP algorithm randomly chooses between an advice-free strategy that guarantees worst-case performance and an advice-following strategy that assumes the predictions are perfectly accurate, effectively tracing a linear tradeoff curve between robustness and consistency.\nThey show that there exists a learning-augmented algorithm for online bipartite matching that dominates COINFLIP across the entire range of robustness, providing improved guarantees regardless of how accurate the advice is.\n\nThey mainly use a primal-dual analysis framework to design and analyze their algorithms, adapting classical techniques to incorporate advice-dependent penalty functions that balance following predictions and maintaining worst-case guarantees.\n\n\nFor the vertex-weighted case, they use a version of a continuous process that incrementally pushes flow to neighbors based on an advice-aware carefully chosen penalty function, prioritizing offline vertices with higher weights and those recommended by the advice.\n\nFor the unweighted case, they propose a different algorithm called PUSHANDWATERFILL, which first pushes flow to the advised offline vertex up to a specified threshold and then distributes any remaining flow using the standard waterfilling strategy, allowing better robustness-consistency tradeoffs than COINFLIP in this setting.\n\nThey also improve the upper bound by designing a hardness construction using two adaptive adversaries, one targeting robustness and the other consistency, which remain indistinguishable during the initial phase, making it provably impossible for any algorithm to exceed certain tradeoffs across the entire spectrum.\n\n\n\n\nThe COINFLIP algorithm randomly chooses between an advice-free strategy that guarantees worst-case performance and an advice-following strategy that assumes the predictions are perfectly accurate, effectively tracing a linear tradeoff curve between robustness and consistency.\nThey show that there exists a learning-augmented algorithm for online bipartite matching that dominates COINFLIP across the entire range of robustness, providing improved guarantees regardless of how accurate the advice is.\n\nThey mainly use a primal-dual analysis framework to design and analyze their algorithms, adapting classical techniques to incorporate advice-dependent penalty functions that balance following predictions and maintaining worst-case guarantees.\n\n\nFor the vertex-weighted case, they use a version of a continuous process that incrementally pushes flow to neighbors based on an advice-aware carefully chosen penalty function, prioritizing offline vertices with higher weights and those recommended by the advice.\n\nFor the unweighted case, they propose a different algorithm called PUSHANDWATERFILL, which first pushes flow to the advised offline vertex up to a specified threshold and then distributes any remaining flow using the standard waterfilling strategy, allowing better robustness-consistency tradeoffs than COINFLIP in this setting.\n\nThey also improve the upper bound by designing a hardness construction using two adaptive adversaries, one targeting robustness and the other consistency, which remain indistinguishable during the initial phase, making it provably impossible for any algorithm to exceed certain tradeoffs across the entire spectrum.", "questions": "None.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper makes a strong contribution to learning-augmented online optimization by introducing algorithms that achieve improved robustness-consistency tradeoffs across the entire spectrum. The authors address one of the most fundamental problems in online algorithms—online bipartite matching—combining elegant algorithm design with rigorous primal-dual analysis and an improved hardness construction that clarifies the theoretical limits of the problem. Empirical results on diverse datasets convincingly support the theoretical claims.\n\nI recommend accepting this paper as it advances both the theoretical foundations and practical understanding of learning-augmented online matching.", "was_revised": true, "final_justification": "I have decided to maintain a positive score for this paper.", "rebuttal": "Thank you for your time and effort in reviewing our work, and for appreciating our contributions."}, {"review_id": "FdxPpl4Pum", "reviewer": "Reviewer_g5iY", "summary": "In this paper, the authors consider online bipartite fractional matching problems when the online decision maker is provided advice in the form of a suggested (offline feasible) matching in each iteration. They design algorithms for both the vertex-weighted and unweighted versions of the problem that are provably better than the coin-flipping strategy of randomly choosing between advice-following and advice-free algorithms. They also show that the vertex-weighted version can be extended to the AdWords problem with small bids. They also provide hardness bound on the robustness-consistency tradeoff and validate their algorithms through synthetic and real-world data.", "questions": "The authors list several interesting open questions in their conclusion. I wonder if they have any comments indicating how some of the content and technical ideas within the paper could be extended or be helpful (or not) in addressing these questions.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Results, claims and proofs are technical sound and solid and provide a good picture on what can be achieved for these problems under learning-augmented algorithms.\n- Paper is very well written, without going into unnecessary technical details within the main body.\n- Content of the paper provides additional and novel aspects to the literature on online bipartite fractional matching problems under learning-augmented algorithms.\n- Novel and well positioned paper.\n\nWeaknesses:\n- Would have been nice to get additional insights on the open problems listed in the conclusion, but this is a minor weakness, as I liked the paper ...", "was_revised": true, "final_justification": "I am fully supportive for this paper to being accepted", "rebuttal": "Thank you for your time and effort in reviewing our work, and for providing useful feedback.\n\nMany of the existing works that study the problems mentioned in our conclusion are based on primal-dual analysis. As such, we hope that our learning-augmented primal-dual technique proposed in this paper extends to these settings too."}, {"review_id": "hVsK6CF07p", "reviewer": "Reviewer_zQgB", "summary": "This paper tackles the problem of online bipartite fractional matching with the support of advice. In this setting, there exists a bipartite graph between a set of offline vertices $U$ that have a value associated with them and a set of online vertices $V$ that arrive one by one. Upon the arrival of each online vertex, its neighbors along with suggested fractional matchings to its neighbors are revealed. The algorithm must then decide, in real time and without future knowledge, how to match (fractionally) the arrived online vertex to its neighbors subject to feasibility constraints.\n\nThe authors present two novel algorithms:\n\n* LEARNINGAUGMENTEDBALANCE (LAB) for the vertex-weighted setting, which adapts the classic BALANCE algorithm using an advice-aware penalty function.\n* PUSHANDWATERFILL (PAW) for the unweighted setting, which introduces a two-phase approach combining targeted flow pushing and traditional waterfilling.\n\nA key contribution is that both algorithms strictly improve upon the baseline COINFLIP algorithm across the entire robustness-consistency tradeoff spectrum, which quantifies the balance between worst-case guarantees and performance under accurate advice.\n\nThe LAB algorithm is also shown to improve upon prior work for the AdWords problem under the small bids assumption, offering better guarantees than the well-known Mahdian et al. framework. On the other hand, PAW is tailored to overcome analysis challenges specific to the unweighted setting and shows strong performance both theoretically and empirically.\n\nAdditionally, the paper provides a new upper bound on the robustness-consistency tradeoff, which is shown to be tight in many cases and improves over previous results. Experimental evaluations on both synthetic and real-world bipartite graphs demonstrate that the proposed algorithms interpolate smoothly between advice-based and advice-free strategies, with performance aligning with theoretical predictions.", "questions": "* In each experiment, it seems like there exists a special value $\\gamma^*$ such that at that level of noise, the CR of all executions of LAB and PAW (with different values of $\\lambda$) and the BALANCE algorithm coincide. This can be seen in the experiments in the appendix as well. Could the authors clarify if there is a theory behind this observation and whether this convergence has theoretical significance? Is this due to advice being entirely uncorrelated at that γ, leading LAB to behave equivalently to BALANCE regardless of λ?\n\n* Can the authors clarify the reason why the PAW algorithm does not extend to the case where the advice is also fractional?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The paper presents two new learning-augmented algorithms: LAB, which modifies the BALANCE algorithm with advice-aware penalties, and PAW, which adds a controlled \"push\" step to WATERFILLING for unweighted graphs, achieving better tradeoffs than COINFLIP.\n* The paper develops a factor-revealing LP to derive hardness results, improving prior bounds.\n* Experiments across a variety of datasets and noise levels confirm theoretical insights.\n\n**Weaknesses**\n* There is an assumption that the advice to the PAW algorithm is integral, while the algorithm generates fractional matchings. \n* I have some concerns with the experimental setup. In particular, I like the idea of having a parameter $\\gamma$ controlling the accuracy of the provided advice; however, the same level of noise is not reflected in the CR of the algorithms simply because the advice matches the online vertices to non-neighbor offline vertices, which are infeasible and the LAB algorithm corrects the infeasibility by matching to other points. (To better understand my concern, see Figure 4: when $\\lambda=1$ (the LAB fully trusts the advice and completely follows it) and $\\gamma=1$ (fully noisy setting where advice is completely irrelevant), the CR is still above 0.9 in three cases). I believe the experiments are more meaningful if the algorithm is tested on valid but poor advice. For instance, I expect to see a CR of 0.63 or so when $\\lambda=1$ and the advice provides a 1/2-approx matching.", "was_revised": true, "final_justification": "My concerns regarding the experimental setup are resolved.", "rebuttal": "Thank you for your time and effort in reviewing our work, and for providing useful feedback.\n\nYou are correct that PAW requires integral advice while LAB can handle fractional advice, and we agree with you that it would be nice if there is a way to extend the analysis of LAB to handle the unweighted case. Unfortunately, this is a limitation of our current analytical approach: our analysis for LAB is independent from the weights, and so it is not obvious to us how to show that LAB attains an improved tradeoff in the unweighted setting. On the other hand, the analysis of PAW depends on the integrality of the advice, and we were unable to find the same bound for the fractional case. We do not rule out the possibility that there is a way to unify the two, and we view this as an interesting open problem to resolve. We will add a clearer discussion about PAW versus LAB in our revision, and motivate this open problem more clearly.\n\nAs for the experimental concern, we would like to point out that the robustness ratio is a provable guarantee that holds for any instance (even worst-case ones) while your concerns of high competitive ratio were referring to random ER (Erdos-Renyi) instances and real-world instances (which are unlikely to be worst-case for our proposed algorithms). The trend you are expecting happens in the synthetic UT (upper-triangular) instances. We would also like to highlight that our advice is always valid: when generating advice, perturbation is only applied for the prediction of the future (excluding current time step), so the advice will only be non-zero on actual neighbors of the arriving vertex.\n\nRegarding your question about coinciding intersection points: Unfortunately, we do not have a working theory explaining this phenomenon but it is an interesting observation that may warrant further investigation in future work. We will mention this phenomenon in our revision.\n\nFinally, for the paper formatting concern, we didn’t notice such inconvenience when submitting our paper. We will fix this issue in the camera-ready version by, for example, matching the numbering of the main paper with the full version. We apologize for the inconvenience and thank you very much for pointing out this issue."}, {"review_id": "f9JIAQABfc", "reviewer": "Reviewer_cUNG", "summary": "The paper under consideration studies the vertex-weighted online bipartite fractional matching problem with predictions. That is, there is a bipartite graph where one side is available to the algorithm upfront offline. Every offline vertex is assigned a weight (if all weights coincide, the instance reduces to an unweighted one). The other side of vertices arrives online one-by-one. \nIn the purely adversarial setting, nodes arrive without any information and the decision maker needs to immediately and irrevocably decide to which extend an edge is (fractionally) added to the matching. \nIn the setting with predictions, there is a prediction for each online vertex indicating to which extend each incident edge should be considered.\n\nThe paper derives algorithms for the unweighted and vertex-weighted setting and derives results for robustness and consistency---a classical approach in the algorithms with predictions literature. More precisely, for the vertex-weighted variant, a learning-augmented version of the balance algorithm is used to derive the robustness-consistency guarantees. For the unweighted case, an extension of the classical waterfilling algorithm is developed. \n\nFrom a technical perspective, the analysis is based on a primal-dual approach. In particular, depending on the arrivals, primal and dual variables are updated in a suitable way to maintain feasible solutions for both problems. These can then be used to apply typical primal-dual arguments for competitive ratios. \n\nThe authors can extend their results also to the AdWors problem when imposing a small-bid assumption and complement results with an upper bound for the integral-advice case.", "questions": "* One of my main concerns is the novelty and originality of the paper: Even though I like the general approach, I got the impression that this work only adds marginal value to the huge body of literature in the algorithms-with-predictions regime. Can you clearly state the main differences why this work is adding sufficiently compared to previous work, please? (In the paper, there is only a small paragraph on page 2 on this unfortunately)\n\n* In the paper, you are required to use two algorithms for the vertex-weighted and unweighted case. Do you see a chance of unifying both settings? More precisely, what is the deeper intuition why these two approaches are required?\n\n* As a follow-up point, can it be the case that the primal-dual analysis is simply too lossy to get reasonable guarantees in both cases?", "limitations": "No negative societal impact.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "*Strengths*:\nThe paper derives reasonable guarantees for robustness and consistency in a variety of settings in online bipartite fractional matching. In particular, the guarantees outperform trivial bounds from coinflip arguments and are extendable to more general settings (as AdWords, with a few reasonable assumptions)---indicating the power of this approach. The primal-dual analysis is nice and clean, making it an enjoyable read.\n\n*Weaknesses*: \nThat said, the paper is required to use different algorithms for the different problem formulations---tailoring the approach to the respective problem. The design of the algorithms feels natural, but not really surprising. Given this design, the primal-dual approach for the analysis is expectable. \nHaving a unified approach for both cases (unweighted and vertex-weighted) would be a very desirable goal.", "was_revised": true, "final_justification": "I keep my score.", "rebuttal": "Thank you for your time and effort in reviewing our work, and for providing useful feedback.\n\nYou are correct that PAW requires integral advice while LAB can handle fractional advice, and we agree with you that it would be nice if there is a way to unify the two. Unfortunately, this is a limitation of our current analytical approach: our analysis for LAB is independent from the weights, and so it is not obvious to us how to show that LAB attains an improved tradeoff in the unweighted setting. On the other hand, the analysis of PAW depends on the integrality of the advice, and we were unable to find the same bound for the fractional case. We do not rule out the possibility that there is a way to unify the two, and we view this as an interesting open problem to resolve. We will add a clearer discussion about PAW versus LAB in our revision, and motivate this open problem more clearly.\n\nIn terms of contribution, we would like to respectfully disagree with the reviewer's view that our work is marginal. Online bipartite matching is a fundamental problem in Computer Science and Operations Research that has been studied extensively. Given the increasing availability of machine learning and AI prediction tools, it is important that the research community studies how such predictions can interface with classic problems to yield provable improvements. Learning-augmented algorithms provide such a principled framework for doing so. However, all prior work that studies the problem of learning-augmented online bipartite matching either considered a restricted special case or did not even beat the performance curve obtained by the naive coin-flip algorithm (see Figure 1 and the surrounding discussion). As such, there was a big gap in our understanding of the problem, and our paper contributes towards filling this gap.\n\nAs the primal-dual technique has proven successful in providing tight analyses for many variants of online matching, we do not currently have reasons to believe that the framework is inherently \"too lossy\". We believe that the failure to unify the two analyses is an artefact of our current approach."}, {"review_id": "yPeUEe16dB", "reviewer": "Reviewer_EhSo", "summary": "This paper studies online bipartite fractional matching with advice and proposes two learning-augmented algorithms—LAB for vertex-weighted and PAW for unweighted settings—that provably outperform existing methods. Both algorithms dominate the naive COINFLIP baseline across the entire robustness-consistency tradeoff, a first in this line of work. LAB further extends to the AdWords problem under the small bids assumption, improving upon classic results by Mahdian et al. The paper also establishes new theoretical upper bounds by constructing hard instances that reveal fundamental limits of any algorithm in this framework. Extensive experiments on synthetic and real-world graphs confirm the algorithms’ effectiveness: they achieve optimal performance under accurate advice and gracefully degrade as advice quality worsens, aligning with theoretical predictions. This work advances the theory and practice of learning-augmented online optimization.", "questions": "No.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths and Weaknesses:\n\nThis paper presents a thorough and impactful contribution to the field of online optimization. It introduces two learning-augmented algorithms, LAB and PAW, for online bipartite fractional matching in both vertex-weighted and unweighted settings. A key strength is the theoretical breakthrough: both algorithms provably dominate the COINFLIP baseline across the entire robustness-consistency tradeoff spectrum—a significant advancement over prior works, which only achieved partial domination. Additionally, the extension of LAB to the AdWords problem under the small bids assumption enhances its practical applicability, improving upon the classic Mahdian-Nazerzadeh-Saberi framework. The authors further provide tight upper bounds on what any algorithm can achieve via a novel hardness construction, and back up their theoretical findings with comprehensive experiments on both synthetic and real-world datasets, demonstrating smooth performance degradation with increasing noise in the advice.\n\nHowever, the paper’s technical exposition could be improved. While the core algorithmic ideas and analysis are sound, several important definitions and procedural steps are presented in a terse or abstract way, making the work less accessible to readers unfamiliar with the topic. For example, the intuition behind the penalty functions and dual constructions could be elaborated with more concrete examples or illustrations. Strengthening the clarity and pedagogical structure of the technical sections—particularly the algorithm descriptions and analytical proofs—would make the paper more readable and broaden its impact beyond the expert audience.", "was_revised": true, "final_justification": "This paper presents a thorough and impactful contribution to the field of online optimization.", "rebuttal": "Thank you for your time and effort in reviewing our work, and for providing useful feedback, especially about a better exposition of our paper.\n\nWe will revise our paper to give more intuition as follows:\n1. Regarding the penalty functions, we mentioned in the full version an intuition on $f(A,X)$ for fractional advice; unfortunately, $f_0(X)$ and $f_1(X)$ for integral advice are mechanically derived from our primal-dual analysis, so we have little intuition for the definition of these functions. Including this discussion in the main version would make the readers better understand our penalty functions.\n2. Regarding our algorithm descriptions and dual constructions, we believe that pseudocodes incorporating the dual construction would help the readers understand our algorithms and dual constructions more clearly. We already provided pseudocodes of our algorithms without dual construction in the appendix of our full version, but we can move them to the main body and add the dual construction part in the revision.\n3. We agree that our analysis for LAB is quite long, and hence, it would be difficult for the readers to follow the analysis in their first reading. We will add an overview of the analysis in the revision."}]

Author rebuttal:

Meta-review: Learning augmented algorithms (algorithms with hints) are a bit niche for NeurIPS, but this is a very interesting paper that received reviews from the LLA community and the ML ones.

The former are more excited than the second ones, but that was expected. 

I personnally believe that LLA is a very promising research direction for the ML community (not just TCS), thus I am happy to support acceptance of this paper, as most of the reviewers.
Decision: Accept (poster)