Efficient algorithms for Incremental Metric Bipartite Matching
Authors: Ritesh Seth
Mrinal Garg
Sujoy Bhore
Sharath Raghvendra
Syamantak Das
Venue: ICLR 2026 Poster (2026)
Keywords: metric bipartite matching
dynamic algorithm
1-Wasserstein distance
Primary area: optimization

Abstract: The minimum-cost bipartite matching between two sets of points $R$ and $S$ in a metric space has a wide range of applications in machine learning, computer vision, and logistics. For instance, it can be used to estimate the $1$-Wasserstein distance between continuous probability distributions and for efficiently matching requests to servers while minimizing cost.  However, the computational cost of determining the minimum-cost matching for general metrics spaces, poses a significant challenge, particularly in dynamic settings where points arrive over time and each update requires re-executing the algorithm. In this paper, given a fixed set $S$, we describe a deterministic algorithm that maintains, after $i$ additions to $R$, an $O(1/\delta^{0.631})$-approximate minimum-cost matching of cardinality $i$ between sets $R$ and $S$ in any metric space, with an amortized insertion time of $\widetilde{O}(n^{1+\delta})$ for adding points in $R$. To the best of our knowledge, this is the first algorithm for incremental minimum-cost matching that applies to arbitrary metric spaces.

Interestingly, an important subroutine of our algorithm lends itself to efficient parallelization. We provide both a CPU implementation and a GPU implementation that leverages parallelism. Extensive experiments on both synthetic and real world datasets showcase that our algorithm either matches or outperforms all benchmarks in terms of speed while significantly improving upon the accuracy.

Published as a conference paper at ICLR 2026
EFFICIENT ALGORITHMS FOR INCREMENTAL METRIC BIPARTITE MATCHING
Ritesh Seth"
Mrinal Garg²
Sujoy Bhore
Sharath Raghvendra*
Syamantak Das!
HIT Delhi
IT Bombay
NC State University
ABSTRACT
The minimum-coss bipartite matching between two sets of points R and S in a metric space has wide range of applications in machine learning, computer vi- sion, and logistics. For instance, can be used to estimate the 1-Wasserstein distance between continuous probability distributions and for efficiently matching requests to servers while minimizing cost. However, the computational cost of determining the minimum-cost matching for general metrics spaces, poses sig- nificant challenge, particularly in dynamic settings where points arrive over time and each update requires re-executing the algorithm. In this paper, given fixed set S, we describe a deterministic algorithm that maintains, after i additions to R. ((1//0.6)))apppooximat -approximate minimum-cost matching of cardinality i between sets R and S' in any metric space, with an amortized insertion time of ++) for adding points in R. To the best of our knowledge. this is the first algorithm for incremental minimum-
matching that applies to arbitrary metric spaces.
Interestingly, an important subroutine of our algorithm lends itself efficient par- allelization. We provide both a CPU implementation and a GPU implementation that leverages parallelism. Extensive experiments both synthetic and real world datasets showcase that our algorithm either matches or outperforms all bench- marks in terms of speed while significantly improving upon the accuracy.
INTRODUCTION
Large-scale online logistics systems typically consist of a fixed fleet of vehicles or robots, while service requests appear dynamically over time. The task is to maintain a cost-effective assignment of requests to servers. For example, the New York Taxi System processes more than 300,000 ride
requests daily with a fleet of several thousand taxis NYC Taxi & Limousine Commission (024))
A plethora of prior studies model this problem as the classical minimum cost bipartite matching Zhao et al. 2019 Ke al.; [019 Tong al.) 2023 Qin et al.) 2021
problem (Tong et al., 2016
Abeywickrama et al. 2021 A non-trivial challenge in adapting minimum cost matching to dy-
namic framework that recomputing matching from scratch whenever a new request arrives computationally prohibitive and slows down downstream decisions: if each assignment depends on full recomputation, the time compute may exceed the time to dispatch taxi, significantly in- creasing passenger wait times. When requests arrive faster than the system can process them, queues build up. causing cascading delays and further degrading responsiveness. This setting raises two key challenges: (i) can we design data structures that maintain an approximate minimum-cost matching while supporting efficient insertions, and (ii) can these structures process new arrivals concurrently while earlier ones are still being handled? Addressing these challenges is the focus of this work. Throughout, we assume that the cost function between locations satisfies the metric propertics.
This connection to metric bipartite matching naturally extends beyond logistics. The 1-Wasserstein distance, a widely used tool for comparing probability measures in machine learning, can be ex- pressed minimum-cost matching between empirical distributions (Villani 2009 Peyré & Cu-
[uri 2019). It has found broad applications in generative modeling, domain adaptation. fairness, and
distributional drift detection (Tolstikhin al. 2018 Liu al. 2018 Cao al. 2019 Balaji al.

---

Published as a conference paper at ICLR 2026
2020 Formally, for two probability measures y and v metric space (X, d), it is defined as Wi(H,
inf / Ixxx d(z, y) dr (z
xell(u,))
where [1; v) denotes the set of couplings of μu and
In many practical scenarios, however, samples arrive in dynamic streams, so the optimal matching may change at every step. Exact recomputation quickly becomes infeasible in high-througe plications such real-time monitoring (Rabin et al. (01T). adaptive learning (Chen et al.) 2018). or fairness auditing (Chouldechova 2017). This challenge has spurred a growing body of work on extending Wasserstein distances richer domains, including graphs, manifolds, and structured biological spaces, where data naturally resides beyond Euclidean geometry (Séjourné et al.) 2021 Kolouri al. [ Haasler & Frossard 2024 Ju & Guan 2025). Beyond machine learning, dy- namic geometric matching also arises in diverse real wealdw applications, such as quantifying similar- ity between evolving datasets Alvarez-Melis & Fusi (2020), tracking longitudinal changes patient data (e.g., MRI scans) Gramfort et al. (2013), and employing matching-bas based metrics, such as the Earth Mover's Distance, in time series analysis Cheng et al. (202T).
ap-
Despite its importance, research on minimum-cost matchings in dynamic settings remains limited and primarily focused on Euclidean spaces. For instance, Goranci et al.] (2025) recently studied the dynamic Euclidean bipartite matching problem, where updates are allowed on both sides of the matching. Their algorithm achieves an O(1 aappoxiapooiiinioionn with sublinear (in n) update time, and has applications such monitoring distributional drift in streaming data. Also (et al. (2009) for a streaming algorithm with similar approximation guarantec under insertions and deletions. However, the framework of Goranci et al. (2025) assumes that both sides of the bipartite graph always contain the same number of vertices. Although the techniques could potentially be adapted to settings with one-sided arrivals or departures, such an extension would require substantial modifications to the proof, which currently relies on balanced instances. Moreover, the framework is designed for low-dimensional Euclidean spaces and does not naturally extend higher-dimensional or more general metric spaces.
[Andoni
These limitations motivate the central question of this work:
Is it possible to design a fast, constant-factor approximate bipartite matching algorithm for insertions that works in any metric space?
This question forms the core of our study. It motivates a formal treatment of incremental match- ings in general metric spaces and establishes bridge between practical applications and theoretical guarantees. We now formally define the problem.
Problem (Incremental Metric Bipartite Matching) Let S be a fixed set of n. servers embedded in a metric space d), Requests R ri, T2.... arrive online, one at a time. At time t, the algorithm has observed requests ri...., and must maintain a matching Ml, C S x fri,...,Ty rr} that pairs each request distinct server S. The cost of a matching is defined as the sum of edge distances, and the objective is to maintain a matching whose cost is within a constant factor of the optimal at all times.
1.1 OUR CONTRIBUTIONS
In this work, resolve Problem I by presenting the first constant-factor approximation algo- rithm for incremental metric bipartite matching that achieves sublinear update time in the num- ber of edges. To the best of our knowledge, this is the first algorithm that applies arbitrary metric spaces while guaranteeing provably fast updates. Our main result is stated below.
Theorem For any 0 < 8 < 1, there exists a deterministic algorithm that maintains an O(1 (8*)- approximate solution for the incremental metric bipartite matching problem sets R and S em- bedded in metric space, with an update time of
On2 logg (3) log(nn))
where a logg 2 and A is the aspect ratio of the metric space.
2

---

Published as a conference paper at ICLR 2026
The total execution time of our incremental algorithm matches the static algorithm of Agarwal & Sharathkumar (2014) while achieving the same approximation ratio. In this sense, our result strietly generalizes their work: it provides the same guarantees in the static setting while additionally sup- porting dynamic insertions.
In addition to its dynamic nature, our algorithm supports parallel request processing, allowing new requests to begin execution even while earlier ones are still running. This design avoids queue build- up and is well suited for many applications, since several core subroutines parallelize naturally. As result, incoming requests can be handled concurrently rather than sequentially, making the algorithm particularly effective in aatched-insertiee scenarios. To complement the theoretical contribution, we provide efficient implementations on both CPU and GPU. In extensive empirical evaluations on synthetic and real-world datasets, we benchmark against standard baselines including a greedy algorithm and (for low-dimensional Euclidean spaces) quadtree-based greedy approaches. Across all settings, our implementations consistently match or outperform these baselines running time while maintaining competitive solution quality.
1.2 RELATED WORK
Classical algorithms for bipartite matching scale poorly in the incremental setting. The Hungar- ian algorithm, built a primal-dae dual framework Kuhn (1955); Munkres (1957), computes exact minimum-cost matching in (n²)) time; even optimized variants under mild assumptions require (n2.5) time Duan & Pettie 2016). Maintaining optimality as new requests arrive is particularly expensive: each update requires Hungarian search step costing ((n²) in metric graphs, process- ing n requests sequentially leads to a total runtime of (nn3). ). Such bounds are prohibitive for large-
scale systems. A recent breakthrough by Chen et al. (2022) achieves almost linear-time time algorithms for minimum-com that some of the techniques maximum- flow algorithm in the incremental edge-update setting with update time m van den Brand et al.) (2024). Our setting, however, is fundamentally different: we must maintain an approxi- mate min-cost perfect matching under vertex arrivals under metric costs. Extending ideas that main- tain approximate flows under incremental updates to instead maintain exact combinatorial structure (such as perfect matchings), while still achieving approximate cost guarantees, appears to be an extremely challenging open problem.
flow in general graphs with polynomial weights. A related line of work shows
the above paper have been adapted to obtain a (1 aapprooxima
Approximation algorithms for minimum cost perfect matchings provide a way to circumvent these barriers. Agarwal & Sharathkumar (2014) gave a deterministic offline algorithm for metric spaces that constructs a 1/80.031 wewposs-approxiiie -aprroxmmate minimum-cos matching in ( time by combining distance scaling with simultaneous augmenting path searches. While this result shows that near- quadratic approximations are achievable in the offline metric setting, directly extending it to an incremental model is difficult: every new request may trigger searches over O(n²) edges, and the distance scaling framework depends on a constant factor estimate of the optimum, which is hard to maintain dynamically. More recently, in the context of metric optimal transport. advances have yielded (1 + -ppproxximtto algorithms running in near-quadratic time Zuzic (003)) Fox (024))
In a different line of work, researchers have developed additive aptroxiiaap algorithms for optimal transport and related matching problems. These include entropiccregullarizatinn baaae based methods Cu-
[uri] (2013): Jambulapati et al. (2019) as well combinatorial approaches Lahn et al. (2019: 2023)
A common feature of many of these methods is that they are highly parallelizable, and several admit efficient GPU implementationss--ee example, Sinkhorn-based approximations Cuturi (2013)
and the mush-relabel-basee approximation of Lahn al. (2023).
1.3 OVERVIEW OF TECHNIQUES
Our incremental algorithm builds on the static algorithm by Agarwal & Sharathkumar (0014). A key
insight of the static algorithm is that it does not operate directly the given metric d(...). )). Suppose w is a good 'guess' for the offline optimal solution and 0 < ó S is a fixed parameter. We construct hierarchy of μ (log(1 (1)5)) progressively "scaled-down" metrics, M,, M, ...... M,--
At the base level Mn. each original distance d(s,, r) is rescaled by a factor of about n/(Ew) (== 1/p) and then rounded up the nearest integer. In this way, a discretized metric is produced in which
3

---

Published as a conference paper at ICLR 2026
all distances fall in bounded integer range, and moreover the optimal matching becomes (nn) in the scaled space. At higher levels (i > 0), the distances are repeatedly shrunk and rounded further, with the shrinkage factor being roughly n² It can be observed that the shrinkage factor grows very quickly with i, essentially at an exponential rate.
Another key idea is to always maintain 1-feasible partial matching at each level. Given a complete bipartite graph G U S, R S) where each edge (r.s) E R x has cost c(r, s), the seminal work of Gabow& & Tarjan (1989) introduced the idea of a 1-feasible matching, which can be used to find an approximate minimum cost matching.
A matching M along with set of dual weights v(-) on the vertices is called a --eessible matching if the following two condition holds
(() + ((s) s scr,,)+ +1, (r, & M,
v(r) y(s) c(r,s),
(r, s) E M.
Given 1 1-feasible matching M., an edge (1, E X S is called admissible, if either (r, 8) is in MI or y(r) + (()) = c(r, 8) 1.
At high level, the algorithm works follows. For any i (initialized to 0), it uses the algorithm by Gabow and Tarjan to compute partial I-feasible matching M' and corresponding duals yı(-) under the scaled metric M,. The algorithm essentially works in phases. Each phase uses a BSS-yty graph search procedure over the admissible subgraph to match several requests via augmenting paths. Duals are suitably adjusted when the search cannot proceed. A crucial twist introduced by Agarwal & Sharathkumar (2014) is that the procedure is halted at level once every free vertex in R reaches dual weight y max (n.
All such free requests (along with free servers) are then promoted to level + and the algorithm now operates in the scaled metric space M,+1. A delicate analysis shows that the number of requests and servers promoted to any level S i S f is upper bounded by n - Hence, each graph search phase can take only n 20(38)) while the number of phases is upper bounded by y! leading to the desired (n2*+) runtime for each level. In case there are free vertices promoted to level J4, they are matched using the standard Hungarian algorithm. However, with suitable choice of parameter, it can be shown that the number of such requests can be only about 2/2 and hence the Hungarian algorithm can take at most O(1²) time.
Our Incremental Algorithm. To extend the above algorithm to the incremental setting, a natural approach is to explicitly maintain (log(11))) 'levels' of I-feasible partial matchings. For instance, when new request rj R arrives, we need to (i) determine the level at which we should be matching it and (ii) efficiently modify the existing matchings and duals at various levels to reflect this change.
One natural strategy to handle both (i) and (ii) is to initialize the new request at level 0 and augment the partial matchings and duals each level, akin Agarwal & Sharathkumar (2014), and promot- ing requests to higher levels as their dual values reach y for any level O S i S μt. However, one serious caveat of this strategy is that we may end up searching through the entire graph just to process single arriving request, which could lead to a prohibitive update time of O(n²).
We overcome this major challenge by departing from augmenting path-based approach to push- relabel styled framework in order to maintain the partial matchings M' at each level 0 < i < μ.. Roughly speaking, a newly arrived request r starts at level 0 and simply looks for an admissible edge in all levels of scaled metric spaces between 0 and We pick such an admissible edge (r, s) E Rx S arbitrarily and execute a 'push'. Specifically, we match r to 8, decrease the dual of the server by to maintain 1 I-feasibility, and in case the server was already matched to some other request r', we make free. In case no admissible edge is found for r, we do a 'relabel' we increase the dual of to an extent where one edge becomes admissible. However, if the dual of r reaches maxx, then is promoted to level 1 and the process continues. In general, this may free up a request at any level i S μ in which case we simply continue the push-relabel from this level. One erucial invariant of our algorithm is that a server that is matched at any level 0 < i < f is only available to requests that level i higher.
4

---

Published as a conference paper at ICLR 2026
The above description might suggest scan O(n²) edges to push single free request; while that can happen the worst case, a careful amortized analysis yields O(n ((n)+)). For each level i the total number of requests ever promoted to is n2 I n (3-0 (by the scaled metric and our choice of w! Each failed admissible-edge search for free request at level 2 causes request dual increment (a relabel) of at least 1, and server dual decrements can be charged to these request increments, so the total number of such searches Ogy, before the request is either matched promoted. Each search inspects (nz) matched servers at levels 2 i (plus one free server), and we assume a data structure that finds the nearest free server in O(1) time (we never search servers matched lower levels). Hence the total work for admissible-edge searches at level i over all arrivals is ( y/ = (n²+ for suitable constants. With only O(log(1/6) levels this yields the stated amortized update time.
PRELIMINARIES
We introduce notations and important definitions that would be required to describe our algorithm. Given (possibly partial) matching M R S, we denote the total cost of all the edges in MI by weMM. Throughout this and the next subsection, we will assume that we are given a value w satisfy- ing we( (o; I < 2w((M), where Mj is the offline optimal solution of requests r1, "r. for any 1 S n. We will show how to remove this assumption in Section 3.2
w-Scaled Metrics. Given a parameter > < 8 1, we define μ + different finite metric spaces Mo...., Ma+1, where < loga (_ and each metric M; is on the points S U R equipped with distance dz(),)) defined follows
2d(s.)) Ew
if = 0,
d(s,)))=
(3)
J-i( 2(1+6)an*i>)
ifi 0,
where ii: =30, 2log,
Define ymaax = 30 y Vi E (0...... 00....,++7
We state two key properties of these metric hierarchy in the form of the following lemma.
Lemma ( [Aaawall & Sharathkumar (2014)) The following properties are true for the distance
functions de(;;))
1. For i 0, :) is a metric.
2. For i 1, there is scaling factor o; such that (1-e/3)o, S d(s,r) S (s,)))
Our algorithm will have notion of levels for each requests, servers, matchings between them and corresponding duals which corresponds to the hierarchical metric spaces defined above. For each level i {0. ... (μ + 1)}. M will denote a partial matching level i and we define the following w.r.t M'. B3 denotes set of servers that are matched in Mi and B = U B3, that is B3s is the set of servers matched in M A i. S is the set of all free servers at any point in the algorithm. For any request or server in R U SS, we will maintain an integer level(-) which will denote the level at which they currently matched. Finally, let (+(+) be dual weights R U S at level i.
We introduce two invariants maintained by our algorithm at all points of time.
(I)) At each level i, the matching M maintained by the algorithm is 1-feasible. That is, at any level E (0.... ,/ + 1}
(s) + vr(r) < d,(s,)) +1 where (s,r) M and E B's (s) + w(r) = d,(),)
where (s, E M.
5

---

Published as a conference paper at ICLR 2026
(12) For any unmatched server (that is E )"); ya(s) any request r, if level(r) = i, then yk (r(r) = 8/ max level(s) i, then (s) 0, vA <
= 0. Vi {o.... (u + 1)}. For
44 - h < For any server s,
INCREMENTAL PUSH-RELABEL ALGORITHM
In this section we give necessary details of our algorithm and sketch of the analysis. The main pseudocode and detailed proof's can be found in Appendix A
Initialization. At the start of the algorithm. all servers are placed in the free-server set S while the sets B's for levels E .0..... 1} are empty (i.e., [B's 0 for a)l level(s) too, Vs e S The initial matching empty, denoted M, {0}. For all E {o..... (u + 1)} and for all s E S*. the dual y/ (s) =0.
We now describe our incremental push-relabel algorithm for handling arriving request ry. The algorithm maintains the current matching M, dual weights for requests and servers at each level, and data structures for admissible edges.
Upon arrival of request ry, its dual weights are initialized to zero across all levels, and it is marked as free request rf. We compute the w-scaled metric distances (.(5)))) :) for all 0 S i < 1 We create sorted list C, of free servers ordered by their distance d(.rr). Both level(r!) and counter are set to O.
Pevemmental-Psh-Reelle
While there a free request rf and S Su++ +1
Admissible edge search. We query LIND-ADMISSBLLEEDDGUYY ,i).
If an admissible edge (r', 8) is found:
s free, we insert (r ss) into M,,, and decrease (:(s) by 1. Moreover,
Extract from C,
Move from 5 to B
Set: level(s) <
" If is already matched to some r', we perform push: replace edge (r',s) with (rf, s) in M,. decrease yı by 1, and perform the following:
Move from B gloeel(r") to B3
Set: level(s) <- i, rl -- v-r,i i-r level(r')
If admissible edge is found, mum slack needed so that at least one edge becomes admissible. The minimum slack computation
perform relabel: increase (r(r)) by the mini-
follows:
* Let sf be the first server in Lyp
* Then the minimum slack quantity
[d,()))) y((() y(()} } + 1.
min xEBBU(sf)
Promotion. If increment by minimum slack pushes y: (r() up ya then the request is promoted upper level by setting: level(r5) +- i 1, i
If there is free request promoted to level + 2, match it to a server at level - 2 or S using Hungarian Algorithm. The resulting matching denoted M,.
Find-Addmissble-Fdge Given request r at level i, we first all servers currently matched levels 2 i (that is, servers E B3')) to check whether any edge (r, 8) is admissible at level i, such a server exists, it is returned. Otherwise, we check the closest free server sf from sorted list C), for admissibility under the same condition. If none exist, the procedure returns ().
We would like to re-emphasize that we significantly deviate from the algorithm and analysis of the static approximation algorithm of Agarwal & Sharathkumar (2014) in major aspects. Firstly,

---

Published as a conference paper at ICLR 2026
while the static algorithms build the levels successively by pushing both unmatched requests and free servers higher and higher, we need to maintain partial matchings at all the levels simultaneously. In fact, in algorithm the level of request increases while that of server can only decrease. Secondly, as highlighted in Section I.3] rather than using augmenting paths, we use a push-relabel framework locally match and unmatch requests. Finding admissible edge is the bottleneck in this operation. Crucially, we use the I-feasibility property of the matchings and dual adjustments to pay for this expensive step.
3.1 ANALYSIS
The costs analysis of our algorithm follows that of the static algorithm by Agarwal & Sharathkumar (2014) while having few crucial differences. The main distinction stems from the fact that in the static algorithm, while analyzing the cost of matching at any level i, the set of requests and servers promoted to level form balanced bipartite subgraph of R U. Due to the incremental nature of setting, the graph we analyze at level is skewed it may have more servers than requests promoted to level i. This introduces non-trivial modifications in the analysis. We provide all the details in Appendix A.2 and prove the following central lemma.
Cost.
Lemma 2
Let Mj be the matching maintained by our algorithm after the insertion of rij and let M2 be the offline optimal matching on that perfectly matches T1, "1. with servers in S. Then (M,)) < 0(1/8)) - w(M3).
) by our algorithm. While the static algorithm creates these duals in successive iterations, maintenance of these duals simulta- neously for all levels is novel contribution of this work.
The cost bound relies on maintenance of the dual invariants (11) and (12)
Update Time. We sketch the update time analysis of our algorithm which forms the technical heart of our paper. Each update consists of three operations: Relabel, where the dual of the active request increased; Push, where the algorithm either matches a free server or an already matched server from the same or higher level; and Find-Admissible-ddee admissible edge. We show that the total number of such operations over n requests can be bounded by On22+5 (1/5)). which implies the desired amortized bound per arrival.
where the algorithm scans for a 1-
Relabel operations. At level i, each request r enters with dual (r) 0 and increases monoton- ically until either it reaches the maximum allowed dual value y or is matched. Thus, the total number of relabel increments per request per level is upper bounded by y!"ax.
Push operations. Push steps are more subtle because they may involve cascading reassignments of servers. To control this, we relate server dual decrements (triggered by pushes) to request dual increments (triggered by relabels). The following amortization allows us bound the number of push operations by the number of relabel operations.
Lemma 3 For any level i, over all the insertions, the magnitude of server dual decrements is upper bounded by the magnitude of request dual increments.
Admissible-edge searches. The most expensive operation naively is scanning for admissible servers, which could cost (nn) per request per level. However, we prove two crucial lemmas that will establish that the amortized number of operations is still bounded by O(n2+d). The first key ingredient the following lemma which upper bounds the number of requests that are promoted to level i higher.
Lemma 4 At any point in the insertion sequence, at level i, the number of requests (and hence the number of servers) matched at level i or higher, denoted by ni, is at most n. n1-,., where d;; Ei ipk 1'11 8.
This bound intuitively implies that search time for admissible edge reduces drastically at higher levels. While a similar property holds for the static algorithm by Agarwal & Sharathkumar (2014), search for admissible edge also need to consider free servers which can be (()) in the worst case. However, we overcome this by simply maintaining a list of servers for every request sorted according to distance. These properties give us the following lemma.
7

---

Published as a conference paper at ICLR 2026
Lemma 5
For fixed level i, the total time spent in admissible-edge searches across all request insertions is (n+)+))
Proof. [Proof sketch] From the previous lemma, only n'- requests are matched at level i or higher at any point of execution. For each such request, we bound the total number of search for an admissible edge by 2ymuax before the request is promoted to level i + 1 (in case it is). To see this, recall the for a free request at level i, the algorithm scans through all the servers that are currently matched at level i or higher plus the set of currently unmatched servers. The number of operations for one such search can be upper bounded using Lemma by ni + 1, where the additional operation happens for extracting the nearest unmatched server. A successful search step, while an unsuccessful search is charged to a relabel step both of which are upper bounded by yfuax for any request level i. This along with Lemma 4 proves the claim with suitable choice of parameters.
be charged to a push
The above analysis does not directly hold for level fu since are running Hungarian algorithm at that level. However, observe that by Lemma 4 nu+2 < nt. Hence, each Hungarian search cannot take more than 1,1+ time. Details can be found in Appendix A.3
Lemma 6 For a sequence of requests T2,T2,"" T2, "..,., ry. the total update time of our algorithm is upper bounded by O(n2+6 -log (1)5)
3.2 REMOVING THE ASSUMPTION ON
Recall that throughout the previous section, we had assumed that we are given an estimate w such that after the arrival of any request rj. m(M)) w S 2w(M)),, where M₁ is the offline optimal solution of requests T1, TT... In this section, we remove this assumption using a standard guess- and-double trick.
When the first request r1 is inserted, the procedure begins with the initial value of w min r1). Suppose that after processing Ty. we find that some level < S (μ 1), the number of requests with level or higher is greater than n I= (where .; 3'-18), 8). Then we double the value of w and compute an offline matching by artificially re-insert the request sequence
: ] with the new value of using our algorithm. We are now ready to finish the proof of Theorem [ as follows
Let us divide the insertion sequence 11, "2, in to l phases Po: P1, Pe such that the value of w 1 at the beginning of Po and was doubled at the beginning of Py for any k Z For O < k S f, let Wa denote the value of at all time points in phase Px. We show in Appendix A.2 A.2 that the cost bound holds as long as w is at most twice the value of the optimal solution. We claim that this property is always true for each phase. We prove this by induction
the number of phases k. Note that this property holds at the beginning of Po by our choice of win = minges d(s, and will also hold at the end of this phase since optimal is monotonic. Now fix any Pk, h: > and let ry be the first request in this phase. By the condition of doubling, w < w(M)) and hence wr = 2w < (w(M) The property holds for all request insertions in this phase by monotonicity of optimal matching.
For the runtime bound, note that our algorithm always doubles w when we find that at some level 0 < < (μ + 1). the number of requests with level or higher is greater than n² 1 We show in the Appendix [A.3 that if this is true, the amortized runtime for a phase is upper bounded by O(n2+6 log" (1/5)). The only thing remaining to show is that the number of phases is upper bounded by log(nA). This follows from the fact that w(M)) S n and hence are done.
4 EXPERIMENTS
In this section we present our experimental results. We developed two independent implementations of our a [T The first one is implemented using C++ and performs all operations the CPU. The second leverages PyTorch, offloading the computationally intensive components of the
Our code is available http://tticaaaaaaaaaa////eommtot Mattraatttte-aacciin----g-l
8

---

Published as a conference paper at ICLR 2026
algorithm to GPU. All the tests are performed machine with AMD EPYC 7763 64-Core Processor and 514 GB of RAM using a single computational thread for CPU bounded tasks. For the GPU bounded tasks we have used NVIDIA A100-SXM4 Graphics processor with 40GB GPU memory belonging to the same machine.
Datasets: We evaluate our algorithm on three real-world datasets and one synthetic dataset, each consisting of 10,000 data points. (i) MNIST. The MNIST dataset (LeCun et al.) contains about 70,000 handwritten digit images, each represented
28 28 grayscale grid (784-dimensional) We sample two distributions, normalize each image so that pixel intensities sum to one, and measure distances using the L1 norm. (ii) NYC-Taxi. The New York City Taxi dataset HH] (202T) provides pickup and drop-off locations. We construct two distributions from trips completed during the first week of a given month, ordering requests by pi ckup dateti me to capture sequential arrivals. (iii) Beijing Road Network. The Beijing Road Network, extracted from large-scale taxi GPS tra- jectory data in |Lin & Zhang (2018) and subsequently processed in Jain et al.] (202T), comprises approximately 31,000 nodes and 72,000 edges. In our experiments, we employ the shortest-path metric as the underlying distance function. (iv) Synthetic. We also generate 10,000 points uni- formly at random in the wwo-iieeniooaal domain [0, 100]3. Additional results for this dataset appear in Appendix
B For NYC-Taxi data and Synthetic data, we employ Euclidean distances.
Adaptation to batch (Batch Incremental PR): Although Algorithm inherently sequential, both of the crucial parts- push and relabel - lend themselves to parallelization. More specifically, we cre- ate an admissible graph with all free requests in parallel. Further, the push step can be executed by adapting a parallel implementation for computing a maximal matching on the admissible graph. Further, the relabel step involves updating entries in a certain 'slack matrix' which can also be exe- cuted in parallel. We adapt the parallel implementation of push-relabel from Lahn et al. (2023) who give an e-additive approximation for optimal transport (and hence also min-cost perfect matching) in the static setting. For our experiments, we assume that requests are arriving in batches of 200 and all requests of a specific batch are processed using the parallel implementation on GPU. We provide additional experiments in Appendix B.2 showing how the average update time changes with varying batch sizes.
Tests: For comparison, we evaluate our Batch Incremental PR algorithm against Greedy, QuadTree- based (QT) and Dynamic Euclidean (Goranci et al. (2025) baselines. Each dataset is sampled 10 times, and the server size is fixed at 10,000. For varying request sizes n E {1000, 2000, ..... 10000), we report the average matching cost and average amortized runtime of all algorithms. In our exper- iments, we set 5 0.001. Furthermore, in Section [. we provide a detailed sensitivity analysis of 6, highlighting its role in governing the nuntime-cost trade-off. In Greedy, for any newly ar- rived request, the algorithm chooses the nearest free server. In QT (Har-Peled] (20TT)) we build a (randomly-shifted or deterministicalll-ssiitee bottom-up: at each cell, greedily match as many red/blue points inside the same cell as possible and unmatched points are propagated (pushed) up to parent cells and matched there (again greedily). We have used CPU based implementation for QT. For Greedy, we have used GPU to compute distance which gives benefits to Greedy process high dimensional data points. We used the open-source implementation of Dynamic Euclidean provided by Zheng (0024) on the NYC-Taxi and Synthetic datasets, as both lie in Fuclidean space. For all experiments, we set the branching factor to 16. How- ever, for Beijing Road Network, we precomputed pairwise shortest path distance since shortest-path computation adds massive computational overhead.
quadtree over the point sets, process tree nodes
Results: In terms of runtime, Batch Incremental PR consistently outperforms Greedy on both MNIST and NYC-Taxi datasets (Figure (b)) Figure (b)) In contrast, both QT and Dynamic Eu- clidean achieve faster runtime on the Taxi dataset (Figure (())), albeit at the expense of higher matching cost. With respect cost, Batch Incremental PR consistently outperforms both QT and Dynamic Euclidean on the Taxi dataset (Figure a)), while performing comparably to Greedy. On the MNIST dataset, the algorithms QT and Dynamic Euclidean are inapplicable since distances are computed using -norm. Furthermore, Batch Incremental PR surpasses Greedy with a significant margin both in terms of cost and update time. For the Beijing Road Network, QT and Dynamic Eu- clidean are not applicable because the metric is based on shortest-pan -ath distances. Batch Incremental PR consistently achieves a substantially lower cost and maintains significant margin over Greedy (Figure (a). In terms of runtime, Batch Incremental PR outperforms greedy till about 7,000 data points (Figure Bb) after which Greedy becomes better. However, the average response time of Batch Incremental PR never exceeds 50 milliseconds. Overall, Batch Incremental PR consistently

---

Published as a conference paper at ICLR 2026
achieves the best balance between cost and runtime across datasets, and crucially, its performance advantage extends beyond wiw-dimensional Euclidean settings.
Maack
Soperds P0
(a) Average cost per request
(b) Average time per request (in seconds)
Figure I: Plots of MNIST data
Anerage Cast vn. Number of Retuarts (r)
Awarage Patch Time por loqueetts humber laguetto I5)
Bahi aurer
Usa
Auurter Hegertl
Hommeer ofgeerrt
(a) Average cost per request
(b) Average time per request (in seconds)
Figure 2: Plots of NYC-Taxi data
(a) Average cost per request
(b) Average time per request (in seconds)
Figure Plots of Beijing Road Network
REFERENCES
Tenindra Abeywickrama, Victor Liang, and Kian-Lee Tan. Optimizing bipartite matching in real-
world applications by incremental cost computation. In Proceedings of the VLDB Endowment doi: 10. 00.14778/44599803450000 URL https: pdf
(PVLDB), volume 14, pp. 1150-1158, 2021.
Pankaj K. Agarwal and R. Sharathkumar. Approximation algorithms for bipartite matching in metric spaces. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 555-564, 2014.
David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 13:21428-22149, 2020.
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. Efficient sketches for earth- mover distance, with applications. FOCS (or technical report / conference version, 2009), 2009. PDF / tech report available online.
10

---

Published as a conference paper at ICLR 2026
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin (eds.), Advances in Neural Information Processing Systems 33 (NewrIPS 2020). Curran Asso- ciates, Inc., 2020. URL pottps://proceestt tobust-ope imal transport....... htmml
neurips cct/papper/22//haat//
Jiezhang Cao, Langyuan Mo, Yifan Zhang, Kui Jia, Chunhua Shen, and Mingkui Tan. Multi- marginal wasserstein gan. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32 (NeurIPS 2019), pp. 1774-1784. Curran Associates, Inc., 2019.
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng. Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 612-623, IEEE, 2022. doi: 10. 1100FFOC55455.2222.00666
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differ- ential equations. In Advances Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Kevin Cheng, Shuchin Acron, Michael Hughes, and Eric L Miller. Dynamical wasserstein barycenters for time-series modeling. Advances in Neural Information Processing Systems, 34: 27991-28003, 2021.
Alexandra Chouldechova.
Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):153-166) 163, 2017.
Marco Cuturi. Sinkhorn distances: lightspeed computation of optimal transport. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 13, pp. 2300, Red Hook, NY, USA, 2013. Curran Associates Inc.
Ran Duan and Seth Pettie. Scaling algorithms for weighted matching in general graphs. Journal of the ACM, --(2) 2016. doi: 10. 145/2822237
Emily Fox. A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs. In 32nd Annual European Symposium Algorithms (ESA 2024), für Informatik, 2024.
pp. 56-1. Schloss Dagstuh--Leibniz-Zennee
Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 1855):0033-1036 1989. doi: 10.11370021809.
Gramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi, and Da Wei Zheng. Fully dynamic euclidean bi-chromatic matching in sublinear update time. In Proceedings of the 2025 International Conference on Machine Learning (ICML), May 2025. URL https: Oral paper.
//openreview, http://wwww....e.tooooaa.aaaaapa wwwp:22lwwwssoooooeoeoeoo w=w.://ooooeeeedggg..0222
Rw http://eooaaaaoooooooooooooooeee
Alexandre Gramfort, Gabriel Peyré, and Marco Cuturi. Fast optimal transport averaging of neu- roimaging data. In International Conference Information Processing in Medical Imaging, pp. 261-272. Springer, 2015.
M Yasser H. Nyc taxi trip duration. htttps:/wwwe nyc taxi- - trip- wwwpp-rriattttonoo aduratiion 2021. Kaggle.
Isabel Haasler and Pascal Frossard. Bures wasserstein means of graphs. In Proceedings of the
27th International Conference Artificial Intelligence and Statistics (AISTATS), volume 238 of Proceedings of Machine Learning Research, pp. 1873-1881. PMLR, 2024. URL https: 7/ /roceediiggs mmw.mlr...........mmmmmm...m..mm preess/220
4aw.rr22222aaaaaaeeaa.a .dff pdf.
Sariel Har- Peled, Geometric approximation algorithms. Number 173, American Mathematical Soc., 2011.

---

Published as a conference paper at ICLR 2026
Jayant Jain, Vrittika Bagadia. Sahil Manchanda, and Sayan Ranu. Neuromlr: Robust &amp; reliable route recommendation on road networks. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.). Advances in Neural In- formation Processing Systems, volume 34, pp. 22070-22082. Curran Associates, Inc., 2021. URL https::/prrceed wew. cc wttpearrrpp.ccpppppppeeeeeeeee/e
http///ppe.felee/ppeeeeeeeeeeeee fttefffaa//eap//01////// #LL///922eeesaaaaaacclceeeeaaaad Paper.
Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct (L/eppl)))))) iteration parallel algorithm for optimal transport. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Acché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11355-11366, 2019. URL http:::ppocceeiiiiiinigen/ neuripg........pp...e........... http:ipps..pppppe2211331 hash/ 222p:222228890888882333882222222
.tmll
Ce Ju and Cuntai Guan. Deep optimal transport for domain adaptation on spd manifolds. Artificial Intelligence, 345: 104347, 2025. doi: 10. 20001//..artim222251144444
Jintao Kc, Feng (Evan) Xiao, Hai Yang. and Jieping Ye. Optimizing online matching for ride-sourcing services with multi-agent deep reinforcement learning. arXiv:1902.00228. 2019.
arXiv preprint
www.aawww..a.aaaaaaoooaaoaaaaaaa hbtpg//ab/11910 06228
Soheil Kolouri, Navid Naderializadeh, Gustavo K. Rohde, and Heiko Hoffmann. Wasserstein em- bedding for graph learning (wegl). Proceedings of the 9th International Conference on Learn- ing Representations (ICLR), 2021. URL htttts::///peeeeeeeeete
net wwt.nnttt/teiddeeeooeoeo.
32
Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83 1955.
Nathaniel Lahn, Deepika Mulchandani, and Sharath Raghvendra. A graph theoretic additive ap- proximation of optimal transport. Curran Associates Inc., Red Hook, NY, USA, 2019.
Nathaniel Lahn, Sharath Raghvendra, and Kaiyi Zhang.
combinatorial algorithm for ap- proximating the optimal transport in the parallel and MPC settings. In Alice Oh, Tris- tan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Ad- vances in Neural Information Processing Systems 36: Annual Conference on Neural Infor- mation Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL ht / http://apprssss.c nips. cc/paper / 14844451863748 0669 Bae 740944788738
/tt.:///000..0../000000000000000 hatp://---asstaaaatCoooooeeeeeee www.rttt-oooooeeeeeecocccc html
Yann LeCun, Corinna Cortes, and CJ Burges. The MNIST database of handwritten digits. http: / //yann. lecun. com/ ctt/cedb//cccccccccccc/ocococ /eeb//ddmmm mn st
Accessed: YYYY-MM-DD.
Jing Lian and Lin Zhang. One-month beijing taxi gps trajectory dataset with taxi ids and vehicle status. In Proceedings of the First Workshop on Data Acquisition To Analysis, DATA '18, pp. 3-4, New York, NY, USA. 2018. Association for Computing Machinery. ISBN 978 17834666444 doi: 10.1 10.1145/3277868.32777777
URL
32778777
Huidong Liu, Xianfeng Gu, and Dimitris Samaras. A two-step computation of the exact gan wasser- stein distance. In Jennifer Dy and Andreas Krause (cds.), Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Re- search, pp. 3165-3174. PMLR, 2018 URL http: http://proceedinga. www.mmr...... wwt.sssss....pp....... liul8d htmll
James Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32-38, 1957.
NYC Taxi Limousine Commission. Nyc taxi trip record data. https:: nyc gov/ page 2024. Accessed September, 2025.
si /alte//cc/bborr/tlt--tr-------r
Gabriel Peyré and Marco Cuturi. Computational Optimal Transport. Now Publishers, 2019.
12

---

Published as a conference paper at ICLR 2026
Guoyang Qin, Qi Luo, Yafeng Yin, Jian Sun, and Jieping Ye. Optimizing matching time intervals for ride-hailing services using reinforcement learning. Transportation Research Part C: Emerg- ing Technologies, 129:10328)) 2021. doi: 10.10166j.rr22221110333999 URL https: www.
sci occienceiin rect com scc//sccii http:/ccenncceeeeeee aance/artic ottp:///aaaaaaaaaaata///////////
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its applica-
tion to texture mixing. In Proceedings of the 2011 International Conference Scale Space and Variational Methods in Computer Vision (SSVM), pp. 435-446, 2011.
Thibault Séjourné, François-Xane Xavier Vialard, and Gabriel Peyré. The unbalanced gromov-wassersten distance: Conic formulation and relaxation. In Advances in Neural Information Processing Sys- tems (NeurIPS) 2021, 2021. wRR/tttps:/prrcceeiii
neurips. httppp/ccccpppppppp..aeeea
Iya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schölkopf. Wasserstein auto- encoders. In 6th International Conference on Learning Representations (ICLR), May 2018. URL
https://cpenrewte
net forum? d= Lor
Yongxin Tong, Jieying She, Bolin Ding, Lei Chen, Tianyu Wo, and Ke Xu. Online minimum matching in real-time spatial data: Experiments and analysis. In Proceedings of the VLDB En- dowment (PVLDB), volume 9, pp. 1053-1064, 2016. doi: (44778//994550929945577 URL
https://wwws hwbp::://www..lbb.... vldb. org/ /twg/vvvv
Yongxin Tong, Dingyuan Shi, Yi Xu, Weifeng Lv, Zhiwei Qin, and Xiaocheng Tang. Combina- torial optimization meets reinforcement learning: Effective taxi order dispatching large-scale. JEEE Transactions on Knowledge and Data Engineering, TKDE.2021.312707 URL /ttp///o.iaaa//// org 1109 2021. 3127077
2023. doi: 10.1 1099
Jan van den Brand, Li Chen, Rasmus Kyng. Yang P. Liu, Richard Peng, Maximilian Probst Guten- berg, Sushant Sachdeva, and Aaron Sidford. Incremental approximate maximum flow on undi- rected graphs in subpolynomial update time. In David Woodruff (ed.), Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, Jan- uary 7-10, 2024, pp. 2998-2998..... SIAM, 2024. 1ttp://0...111111111111111133391
doi: 10.1137/1.970 1717799971111117992221.. URL
106
Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, 2009.
Boming Zhao, Pan Xu, Yexuan Shi, Yongxin Tong, Zimu Zhou, and Yuxiang Zeng. Preference- aware task assignment in on-demand taxi dispatching: An online stable matching approach. In Proceedings of the 33rd AAA/ Conference on Artificial Intelligence (AAAI), volume 33, pp. 2245- 2252, 2019. doi: 10. 10.1609/aaai.vvo 1.3012122..2155.
/RL/ttts:://js.aaaaaooo index.
php/ APPP/AAAT/A httta//atcllleeeew////aeaa
David. Zheng. Dynamic euclidean matching.
https:://gtthub.com///m
dyn dyn-euc saa-euucmmcchh match, 2024.
Goran Zuzic. A simple boosting framework for transshipment. In 31st Annual European Sympo- sium on Algorithms (ESA 2023), volume 274, pp. 104-1. Schloss Dagstuhl-Leibnnzz-Zeettrm für Informatik, 2023.
A APPENDIX
A DETAILS OF ALGORITHM AND ANALYSIS
A.1 ANALYSIS
Our analysis consists mainly of two parts. In section A.2
we establish the competitive ratio of
algorithm Next, in section A.3 we show that the total runtime of the Algorithm I
is O(n2+0). We
13

---

Published as a conference paper at ICLR 2026
Algorithm PUSREM
Input: The j-th request r,, where E (1....,1)
Output: Matching M, after macthing rj
1: My f- M
2: 3:(r;) + 0 for all (O.....
3: rf tr
free request
4: f,, CREATE- CREATE-SORTED- MORTED-EDGE-LISSE
5: i+0
6: while of + and i S (n + do
7:
if yr(rr) y then
8:
i it1
b promotion of rJf
9: level(r") ti
10:
continue
11: end if
12:
< FINO-ADMIISSBLL-EEDOREYY,,
if' o 0 then
14:
if's E 8 then
>> free server
Add edge (s,r() to M,, (s(s) t Vs(s) -1
16:
> Relabel decrease server dual
17:
r level(s) ti
18:
S 5
{8)
20:
Remove the first element from C,,
update Cas
21:
B's - B (s}
22:
else
23:
Add (s, r to M, let r' be the request matched
b Push server matched to r'
24:
25:
Remove (s, from M, adjust the server dual: (e(s) + (s)s)
27:
r +
28:
level(s)
29:
B Blevel(r')
B
Blevel(r)) {s}
30:
B3 t BB (8)
31:
i it (evel((r)))
32:
end if
33:
else
34:
Let be the first server in CJ
slackmin + min (((s,))-((rf)) s(t) 35:
+
slackmin + 1), 8/ max)
Relabel: increase request dual
37:
end if
38: end while
39: if r * and (r') (μ + 2) then
40: Use Hungarian algorithm match rf with servers in the set B S
41: end if
42: return M,
Algorithm CREATE-SOnee SORTE----SRREE-EE-LLLSSYYY
Input: Request
Output: Sorted list free servers 8 over d(.,r)
1: L (0]
2: for s E do
3: L ((s,U((s,((sr)))
4: end for
5: SORT(L) based on d(.,r)
6: return
14

---

Published as a conference paper at ICLR 2026
Algorithm 3 FIND-ADMISSIBLE-EDGEEI
Input: Request r and its current level i
Output: A server having admissible edge with if exists
1: for E B's do
> Find an admissible non-free server
2:
if' (s) + vr(r) (s, r) then
3:
return s
4: end if
5: end for
6: Let sf be the first server in frr
Find admissible free server
7: if (s((s) + v;(r)= ds(s ()) then
8: return
9: end if
10: return
state two easy but crucial observations about the algorithm INCREMENTAL- SEELL-PUUS--AAAAEEE RELABEL which will be used at various parts in the analysis.
Observation 1 For any S j S n, the algorithm maintains a matchhng M, of the request sequence f2,, -Ty Moreover. once server is matched, it never becomes free.
The first observation follows from the simple fact that we run the main loop until there exists a free request (recall that requests can become free and matched during the processing of new request). It is unclear at this point why the process should terminate. However, we prove in Section A.3 that indeed does.
Given matching My. define M;, as the set of edges (s, E My such that level(r) = level(s) = we refer to such an edge as a matched edge at level i.
Observation 2 For any r E R, level(r) is monotonically increasing while for any S. (evel(s) monotonically decreasing over the sequence of insertions.
Both the observations follow from the fact that in FIND-ADMISSIBLE-EDGE for any request the algorithm only considers edges to that (rvel(r) < level(s).
We prove the following invariants for any matching Mi), S S n. introduced in Section
(II) At each level i, the matching M; maintained by the algorithm is I-feasible. That is, at any level E {0..... (u+ + 1)} (s(s) + (r)r) s ds(s,r) +1 where (s, r) & MI and B3 (s) + (r) d,
where (s,r) E M
(12) For any unmatched server (that E Sh); (s(s) any request r, if level(r) i. then (r) = yk 40 K k < i. For any server s, if level(s) = i, then (s) = 0, vo < k
0. Vi {O.... (H + +)}- For
max
Lemma 7 Invariant (12)
For any unmatched server S", (1(s) = 0o < i S (μ 11) For i, then (r(r) = max vo < k i. For any server 8, if level(s) = i,
any request> r, if level (r)
then ()((s) = 4O < k <i
Proof. The first claim follows from Observation and the fact that for a server in S ()(s)) is set in the initialization phase.
The second claim can be proved using induction on i. For the base case (i = 0). the lemma holds vacuously. Now consider any level i 1. Firstly, by induction hypothesis, (r) = y max 0 < k < i i- Further, since is matched at level i, there exists some iteration when it became a free vertex at level This implies ys-1 (r) was set to y at some iteration. Furthermore, dual increments of happen only at the relabel step and the only dual values that are modified in subsequent iterations are (r) for 2 The third claim follows from an analogous argument for the servers.
15

---

Published as a conference paper at ICLR 2026
Lemma 8 (Invariant (11) The matching WI maintained by Algorithm 7 is always I I-feasible.
Proof. We proceed by induction over updates to M. Suppose 1-feasibility holds after processing r--1- Consider any dual update during the processing of r-- Duals change only in three places: two for servers and one for requests. We argue these two cases using contradiction.
Case (request update). For contradiction, Iet us assume Invariant (11) is violated for request r at point of time when level(r) = i. Recall that the dual variable y:(r) is increased by least and only if there is no admissible edge from any E B U C. We want to show, r maintains feasibility condition with all the servers of B's L C.. We can ignore all server s' E B where since Observation 2 eliminates the possibility of (s', rs) being matching edge in future. If r is matched request, its dual does not increase. Thus, r a free request at level with no admissible edge. After increasing (:(r), suppose for contradiction that feasibility is violated on some rs, where & E 3 C, i.e.,
i,
yı(s) + v:(r) 2 ds
By induction hypothesis, just before the update we had equality (is)) + (:(r) (s r) + 1, so r) was admissible. Since was free, the algorithm would have matched it, contradiction.
Case 2 (server update). When request with level(r) = i matches server E B'g, the dual of 8 is decreased by By induction hypothesis (s, was non-matching 1-feasible edge before the update. Hence, decreasing y (s) cannot violate feasibility.
Thus all updates preserve 1 I-feasibility.
A.2 COST ANALYSIS
After matching y, let M, and Mj be the matching by the algorithm and the optimal matching (under d(s)))) respectively. w(MM,) and w(Mj) denote the cost of the respective matching under metric d(ss)). )). Similarly, ((M,) and ((M)) denote the cost of the respective matching under metric d((,,)). We shall show that w(,,) = (L1)))))(MM)) For our analysis, we assume that we maintain the guess w such that w(M S w S 2w(M)): Vjj E (I....,n..
First, us explore a few properties of the metric space defined by the distance function d,(;))) )). Let Mj C M, denotes the set of matching edges at level Let Sj B3S U. Let RJ. be requests such that for any Ri: level(r) 2 i.
Lemma 9
follows from Agarwal & Sharathkumar (2014). However their notion of server sets used the lemma different ours. Specifically, SJ. contains servers which are both free or matched at any level or higher. Although the methodology of our proof is more or less similar to them, our proof departs at certain places from them due different definition of server set. For the sake of completeness and readability, we present the full proof of the said Lemmas.
Lemma' 9
1. For any i 2 O, de(-,-) is a metric.
2. For i 2 1, ds( r) 2
6 ? for any (s,r) E S} x R
3. For any 2 1, there is scaling factor o; such that
(1 (1-:/3)o,d((srr) S d(s,r) s (s,)s
Proof. Proof of part (i) Given three points a, b and e in the metric space defined by the distance function d(.,)), from the triangle inequality
d(a,b) b) + d(b, c) 2 d(a,c)
The inequality holds even if we multiply it by some & R as follows
[kd(a, 6)] + [d c)1 2 [kd(a, c)]
Using this scaling property of the metric space, will complete the proof of this part. The distance function is defined by d). We use induction on When O, we set Ew where is
16

---

Published as a conference paper at ICLR 2026
the total number of requests. We have .)(+;)) satisfying the triangle inequality. Assume d; (., satisfies the triangle inequality. Setting i 2(14e)9pffr and d(...) d:-1(;.). we have d, (::
satisfying the triangle inequality.
Proof of part (ii) Consider request
Ri is matched at level i. Then for any level 0 I k < i, Moreover Invariant (12) ensures, for any server Sj.
yn maax following Invariant
(2)
yu (s) = O. Then, for any edge (s, r) 5} x Rij the following holds.
30 nt < (8,r) +1
yu (8) ys (r)
&
This implies, ds, 2 30 n 1. So, Vi > O, we have
ds 2 d(-1(5,T) 2
3
12
2(1 + =) 2(1 + 03
since e 2loga
Proof of part (iii) Ignoring the ceiling operator in the scaling of distance only decrease the value of d.(...), so using repeatedlly we obtain
1 d(s,)) & de(s,r)
d(s,r))
where, d; _ 4, On the other hand,
(s S 2(1 + 2) (s,
By expanding the recurrence and performing the necessary algebraic manipulations, arrive
dsss d(s,r) +2
Now using part (ii) of the lemma, we obtain
(1 - e-33)) s d(s,r) s rs)
Corollary For 2 1, let and M' be two (possibly partial) matchings of Sj. Ry.
1. If M is perfect matching, then W ((M) Y, where s is the number of requests in Ri..
2. (1 -
MM
60 M)
MIMP
(M
WM
For the next lemma, let Mj denotes the optimal matching between Sj and Rý under metric d(.,)). This implies M² Mj.
Lemma 10 For all (0.... (u 1)}, the following holds
w(M)) (1 (2)
Proof. Observe that, for every edge (s,r) E Mc (s(s) (r(r) = d, r) and for every vertex E 5/+1 U n2tt sx(x) 2 0 (follows from Invariant (12)). Therefore,
((M)) < (a(v)
VESTUNg
For every edge (s,r) E Mj (()) +(() < dg(s, r) +1. Every vertex of Ri is incident on exactly edge of M)
17

---

Published as a conference paper at ICLR 2026
Σ 91(us Σ RESjURj
+ ((()) +
(s,))MM
Consequently,
x(M)) - (MM)) + 7
(5)
We prove the lemma for cases = 0 and separately:
Case = 0: From the equation have ūi (M])) S ((M)) + j. Since do)
2d(s:r)
and
S 2(M))), we obtain the following inequalities:
xMM)) v
Σ
2n _ d(s,,))+1) + Ew
(s.r)EM
2n
1 w/ (MM)) 2j.
Ew
((M)
2n
Σ
d(s,r) ew
2n
(M))
(s.r)EMd)
Combining the above equation 6 and and using 2w(M)))
w (M")) S w(M,) + sw S (1 + (2)
Case > From 5 and Corollary 11. we get
((M)) & (M3) + s (L+)/))(MM))
Finally by Corollary 2
1 E/6 w(M)) < 1- - e/3
w (M $ (1 + e)o(M)
Lemma 11 For all i E (0,-.. (0 1)}, the the following holds
w(M, s 3(1 3(1+ (M)(;))
Proof. Observe that M), @ Mj results in set of vertex disjoint alternating cycles and alternating paths. For our purpose, we only care about the set of paths denoted by P. Each path in P connects some server of 5/+1 to request in R ic. [IP] = %+1- Using lemma 10
Σ Σ d(s,r) = w(M) w(M) s (2+ (M)) < 2(1 + c)w(M))
PEP PEP (s.r)EP
Recall that d(-, satisfies the triangle inequality, so if the endpoints of path P& E Pare (sk, Tk) S5+1 x R2, then d(sk,TT) E(oner d(s,r). Hence,
w(M Σ Σ d(s,r) 2(1 211++10 =)w((M)
PEP (s.r)eP
18

---

Published as a conference paper at ICLR 2026
Theorem Let M,, be the final matching and M, be the optimal matching, then w(M[n) = (11/80)00 p/()
where = logg 2 x 0.631
Proof.
Using lemma 10,
(M.)) Σ
(MM - (1 2s)
Σ w(MM < 2(1 Σ w(M))
1=0
By applying lemma 11 repeatedly, we obtain,
w(M)) s 21 (1+++) Σ (())) = 2 2)$ Σ
w w(M)
1=0
Hence,
(M,)) < 2(1 ()o
Σ 21(1+))
Putting the values of f and e, we get (1 + t) = O() and 2 = 0(1/8%). Hence (M,)) O(1/8")w(( (M,)
A.3 UPDATE TIME ANALYSIS
Now, let us focus on the run-time analysis. Recall the notations one more time. After n requests has arrived, M,, denotes the online solution and M the offline optimal solution. M;, C M, denotes the set matching edges at level i. Sj = Bi U S and Rj is the set requests such that for any r E Rj; (evel(r) 2 i. M denotes the optimal matching between S and Ri under metric d(.,.). This implies M = M₁
We compute the total running time of INCREMENTAL- SARREMENTAL-PUSI-REEE PUSH-RELABEL over arrival of requests. Recall that we are assuming that our metric space has bounded aspect ratio A. This impacts the cost by a factor of log(nA).
To process j-th request, SNCREMENTAL-PUSH-RREE of levels:
performs four major operations regardless
Creating sorted edge list For each newly arrived request r, the algorithm constructs the
lists L,i using SREATT-SORTTED-EDG--LLA
Push operation. This step involves modifying the current matching by either adding or removing edges. Each addition or removal of an edge is accompanied by corresponding decrease in the dual variable associated with the server of that edge.
Relabel operation. In this step, the dual variable of request is incremented.
Finding admissible edges. For a free request r, FIND-ADMISSTBLL--RDDOO either identifies server from the B' C, that forms an admissible edge with r, or reports that no such server exists.
Now we proceed with the analysis the following way. lemma (Lemma 1.5) runtime of the Relabel operations. Next in lemma 16 we establish that total the runtime of Push steps is upper bound by total number of Relabel operations. lemma 18 we bound the runtime of finding admissible edges. We also argued that if some requests reach at level μ + 2 and matched by Hungarian, the number of such reguests are significantly small and thus the total runtime spent at level 2 is O+n2+)) (Corollary 2). Finally in theorem we prove the bound of the runtime of INCREMENTAL- SAAIANTAL--PU-----AASSS PUSH-RELABEL. We address the runtime of CREATE- SAREEE--OEE----E DORTED-EDGE- LIST inside in theorem
we bound the total
19

---

Published as a conference paper at ICLR 2026
Lemma 12 At level i (I + for any request r, the total number of Relabel operations is upper bounded by yi
Proof. Consider request enters level i. By construction, its dual variable is initialized as yr- upon entering this level. A relabel operation level strictly increases yr. In particular, each relabel increments yr by least one unit. Since yr cannot exceed y the number of relabel operations that can be applied to within level is bounded by y.ax
exits level and progresses fore, no additional relabel operations for r can occur at level i. Combining these observations, we conclude that the total number of relabel operations performed
Moreover,
higher level, it cannot return level i. There-
in level i most y, ymmax, D
Recall that 33 is the of servers matched level Let R$ be the set of requests such that for any r E RR; level(r)
Lemma 13 After matching j-th request, at each level i S (p + 1), we show that
Σ
(s(s)
S Σ vr(r)
SEB'S
PER:
Proof. We establish the lemma using an amortized analysis.
For any server E Bg, define its potential at level as
(5) = (s)
By Observation every server with non-zero dual value must belong to the matching Mj. Conse- quently, for any edge (s,r) Mi level the feasibility condition implies
(s(s) + w ds,
Since ds,,)) 2 0 and (s) I 0, it follows that
(ssrr)s((1))
Moreover, rearranging yields
d.(,,)) (((r) vi(s), that vl((s) v((8) yr(r) r. Because all of ds,rr)), (T), and (s) nonnegative, further obtain
(b(()) S vr(r).
Summing over all matched edges at level i, get
Σ (ssss) Σ v(()).
E
Since, EoeBy vh((s) = EveBy vi(s) we conclude the lemma.
Following Lemma 14]is followed Aromwal & Skarathkumar(2011 and is crucial to the analysis of runtime. For the sake of completeness
providing the complete proof.
Consider M,, the final matching executed by the algorithm. Let m; be the matching at level i or above (i.e. m; = Ugt]Mi and n; be the number of requests at that level or above, then the following holds.
20

---

Published as a conference paper at ICLR 2026
Lemma 14 At any point in the algorithm, any level i, n4 S n'-9, where D; -E Pb
3'-1 and E ( (u + 2)}.
2
Proof. We claim that
(MM)) S -- n-
Suppose this claim is true. Then ni S nnt=:; 4: because (MM)) 2 2ns by Corollary 1 1). Thus it
suffices to prove equation we prove by induction on For, = O, ds r) - - 2m d(s, r). Since w 2 w/M we have,
2n ((M)) 5 w( (M,)) -
4n
This implies ((M)) S 5n
By induction hypothesis, let us assume that
5 s -n --
wh (M,
From lemma 10 lemma
11 equation and corollary
22), we can write
2+ w(M d)-1) v 1- e/3
5 P.-1
W(M - 2(1 + s)-n
w(M,, dz-1) denotes the cost matching M under metric di The last inequality in equation
follows because < ž. On the other hand, by lemma (2).
d, (s,
(1 =/6)d d((s,)))))))))) -15
2(1 + 8) 2
Therefore,
d,(s,)) & (s,1
(10)
2(1 - E) 2
Combining equation Jand equation 10 we get,
5 n <
@( (MM)) 1-1-. P.- -
1-b.
g
We bound the total runtime of Relabel operations.
Lemma 15 At level < (p + 1). total number of relabel operations over all arrivals upper bounded by (ymax n I...)
Proof. Lemma 12 upper bounds the total number of relabel operations by any request with level(r) by y max
Lemma [4 together with Observation 2 implies that at any point of time of execution of INCREMENTAL-. PEENMENNAI--PUUH---P PUSH-REIABBLL. maximum number of requests at level does exceed n 1-1,, This conclude the lemma.
Now bound the total runtime of Push operations.
21

---

Published as a conference paper at ICLR 2026
Lemma 16 At level i S ()) total number push operations over all arrivals is upper bounded by (v) n2" n))
Proof. Each Push operation consists of single dual decrement of some server. Lemma 13 upper bounds the total dual decrement of servers by total increment of requests matched at that level. How- ever, maximum number of requests at level does not exceed n² 11-0,, by Lemma and Observation and the dual of any request upper bounded by y! Hence the lemma.
We proceed to bound the cost of finding admissible edges. Let us bound the time taken by a single call to FIND-ADMISSIBLE-EDGG.
Lemma 17 At level S (p + 1), FIND-ADMISSIBLE-IDGE takes (1) to report an admissible edge.
is dominated by the size of the set |B']]- Indeed, checking the admissibility of an edge incident to free server requires only ((1) time, since the data structure L is maintained explicitly. Therefore, bounding [Bg] by O(n2-4:) suffices establish the lemma.
Proof. The runtime of
By definition, B's is the set of servers matched at level or higher. Note that the number of matched servers is always equal to the number of matched requests. Now we argue the upper bound on matched requests at level i. From Observation 2 once a request is matched at or above level can never subsequently be matched at a lower level h < í. Hence, the number of requests matched level i or above is monotonically non-decreasing throughout the execution of the algorithm.
Finally, Lemma establiishs that, over all arrivals, the total number of requests matched at or above level i is bounded by O(n' -.)). Consequently, the same bound applies to [B's), which completes the proof.
In the following lemma, bound the total cost of finding admissible edges through all requests level i.
Lemma 18 At level i S (p + 1), over all arrivals, total time taken by FIND-ADMISSTBIE--RDGE is 0
Proof. Lemma shows that any call to FIND-ADMISSIBLE-EEDOE requires O(n)~9)) time to find an admissible edge. Each invocation of FIND-ADMISSIBLE-EDGGI is immediately followed by either a Push operation or a Relabel operation. Furthermore, Lemma T6 guarantees that the total number of Push operations is upper bounded (y/max n -1 and Lemma 15 guarantees that the total number of Relabel operations is upper bounded (y/Taxx n n1-P1). -1). Thus, total runtime of finding admissible edges at level becomes 2 ")mxx). We have, ymmax 0 ( ). Together, the running time level i becomes O mn= n222).).
(3 1) 6 - = -2
2 6 = 5
(11)
Hence the runtime becomes O n 2+0
Now we analysis the total cost spent by SICREMENTAL-PUSHIE RELABEL at level μ + 2. At level PUSHL--LPUU---LEEEEEE
μ 2, we resort the Hungarian algorithm to compute an exact minimum-con perfect matching for the subgraph induced by the requests that have been promoted to this level. Lemma 14 guarantees that the number of such requests, which we denote by 2 is at most O(n²). The server set at this level, B U S", has cardinality at most n. The Hungarian algorithm, when applied to a bipartite graph with 2 requests and up n servers, has time complexity of O(1 n log n) by using Dijkstra's algorithm with potentials to find each augmenting path. Substituting the bound n2+22 = O ) the cost of processing a single request that reaches this level is (())
Over the entire sequence of n insertions, the total time spent level μ + 2 is therefore bounded by the number of requests that ever reach this level multiplied by the per-request cost, i.e., O(n
22

---

Published as a conference paper at ICLR 2026
(+) Ö(n -n+ Ö(n (2)). For d S 1, this is ((n which is within our desired bound.
This leads to the following corollary.
RELLLLEELLL Corollary 2 Over all arrivals, total time spent by INCREMENTAL-PUSHI RELABEL at level (μ+ 2) is O(n2+)).
Theorem The amortized runtime of INCREMENTAL- RELUUEL is O(n ++6 log (!)).
Proof. We partition the runtime analysis into tWO. First we compute the total runtime spent over all levels i E (O...., (μ++ + 1)} over all arrivals. The runtime the algorithm depends on four major operations. A single invocation to CREATE-SORTED- SORTED-EDGE--LEE LIST takes no more than ( (μ+ 1)). The factor of (n + 1) appears because computing scaled distance between a pair of points can take -( Thus, over all, CREATE-
costs O ((+((=+))) Now, we examine the runtime of each of other three operations for fixed level i. Following lemma [2] total time of relabeling level i is (n!-w,, ymar). Same bound holds for total numbers of push steps following
lemma 16 Total time taken by FIND-ADMISSIBLE-DDDG is O(n² 2-24. y, y! time. Following
lemma 18 this quantity is O(" 0(-2)) Hence, the runtime of INCREMENTAL AUCEEMENTAL-PUSS-RRELLARR
level i is 0 2===)) ). For finding minimum slack, its runtime is linear to |8%). the same analysis
of runtime of FIND-ADMISSYBLL--DDDO applies. This contributes additional O n n= time factor to the runtime of INCREMENTAL-PUSSE PUS---EAAEERLLLLLL Finally we need update list C, for each request whenever r is matched to a free server. Each time we match free server, updating this data structure costs O(1) time. Since for each request arrival, we find exactly one free server match, the cost of this step becomes (n) over all arrivals.
Recall that, ε 2 log, (1/5)) From Corollary 2 and summing over all O(loga())) many levels, we get total runtime to be 2+6 log" (3)).
B ADDITIONAL EXPERIMENTS
We show our tests and results on the Synthetic data set as described in Section
Tests: Similar to NYC-Taxi data, we evaluate four algorithms: Batch Incremental PR, Greedy, QT and Dynamic Euclidean. In this setting, the server set is fixed 10, 000 and we ô 0.001.
Results: Batch Incremental PR consistently outperforms Greedy in both cost and runtime. Although QT achieves the best overall runtime performance and Dynamic Euclidean becomes second best, Batch Incremental PR surpasses both QT and Dynamic Euclidean by a significant margin in terms of matching cost (Figure 4 a), Figure ()).
Bxciden
(a) Average cost per request
(b) Average time per request (in seconds)
Figure& 4: Plots of Synthetic data
B. 5-SENSITIVITY ANALYSIS
The parameter& governs the trade-off between runtime efficiency and solution quality: larger values bias Batch Incremental PR toward achieving lower matching cost, whereas smaller values prioritize
23

---

Published as a conference paper at ICLR 2026
faster execution. To study this trade-off empirically, we evaluate the algorithm on all datasets using E {0.001, 0.01, 0.13. For each setting, we record both the average response time and the resulting average matching cost. The results, summarized in Figures 5 6 and g illustrate how the choice of 5 affects performance across different data characteristics.
Across all datasets, the runtime consistently decreases 5 becomes smaller: the fastest execution is achieved at 5 = 0.001, while = 0.1 yields the slowest. The cost trend exhibits the opposite behavior. The largest value, typically results in the highest cost (or is comparable to 8 = 0.01). The intermediate setting, 8 = 0.01, usually lies between the two extremes or becomes competitive with ō 0.001, Overall, these results validate that I provides a smooth and predictable mechanism for navigating the runtime-cos spectrum.
0.1, consistently produces the lowest cost, whereas 6 0.001
Aeriage Cuid with offineet
Dusiage Mithh Tirr Falg with tnroed cadtas
Arran:
2006
38.80
2000
-000
(a) Average cost per request
(b) Average time per request (in seconds)
Figure 5: Cost Runtime of Beijing Road Network for 5 E f0.001, 0.01, 0.13
125
(a) Average cost per request
(b) Average time per request (in seconds)
Figure 6: Cost vs Runtime of MNIST for 5 (0.001, 0.01, 0.13
Auerago Carl in dfferuc dafos
sige March Tirra par Marquest with difieredd
3.502
(a) Average cost per request
(b) Average time per request (in seconds)
Figure 7: Cost vs Runtime of NYC-Taxi for d E (0.001, 0.01,
B.2 EMPIRICAL ANALYSIS OF BATCH-SIZE-RUNTII TRADEOFFS
Throughout all experiments, we fixed the batch size of Batch Incremental PR to 200. This choice does not necessarily yield the best runtime performance. To illustrate this, we evaluate Batch In- cremental PR on the Beijing Road Network using batch sizes {100, 200 ... 1000). The results (Figure 99) show that the smallest average matching time is achieved at a batch size of 1000, whereas the largest is observed at batch size of 100. However, this does not indicate monotonic improve- ment with increasing batch size. While the runtime steadily decreases from batch size 100 to 500, begins to fluctuate for batch sizes between 500 and 1000.
24

---

Published as a conference paper at ICLR 2026
08:03- 241
(a) Average cost per request
(b) Average time per request (in seconds)
Figure Cost vs Runtime Synthetic for d 0.01, 0.1}
response
0.02
260
560
520
940
500
Figure 9: Batchsize-Runtime plot
B.3 VARIANCE PLOTS
Following show the variance plots of Batch Incremental PR different data sets.
Mean Inalances Batch horementat Ave agge Cadc Number Requerts
Hean - old scisee indranees
302132
4octc3
2003
6023
100re
F31G
2000
110r
(a) Variance over cost
(b) Variance over runtime
Figure 10: Variance plots on MNIST data
Mows Std across indta
Noat 511 across instanoes
smoone
044
064
1300
0.2
Foot
608
(a) Variance
(b) Variance runtime
Figure 11: Variance plots of NYC-Tax Taxi data
C LLM-USAGE
L.MM have only been used to check for typos and grammatical errors.
25

---

Published as a conference paper at ICLR 2026
Ness scmess rcturoed
Next acrees intanoes
Seich unnental IT:: Aeurage Tequued
064
0041
600
9000
2000
0030
1800
(a) Variance over cost
(b) Variance over runtime
Figure 12: Variance plots on Beijing Road Network
inttacess Sutch rxtemmniaal IC ovarage Los Nurtze: Requipo
Neat acrees instaroes
nasemoniaa festage Hopazzs
6030
300
4000
6900
0030
12509
(a)
Variance over cOst
(b) Variance over runtime
Figure 13: Variance plots of Synthetic data
26


Reviews:
[{"review_id": "wRX1ZE8yrV", "reviewer": "Reviewer_JkD6", "summary": "The paper presents the first streaming and batch-adaptive algorithm maintaining a constant-factor approximation the metric bipartite matching problem. The described algorithm builds upon a previously known algorithm for the offline setting, while making sure that update steps can be executed quickly (when one does amortized time analysis), whereas the worst case is of higher update time. The authors achieve this by utilizing a data structure tailor made for these updates, and by maintaining a collection of partial matchings with a specific property that are a good approximation of the desired matching. Each partial matching corresponds to a different \"discretization\" of the metric space, at different degrees of refinement. The authors support their theoretical results by empirical experiments.", "questions": "Where does the algorithm break if the distance function is not metric?\nA couple of typos:\npage 4, line 189: $\\theta$ should be $\\Theta$.\npage 5, line 247: $B^i$ should be $B^j$.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is an important contribution in the field of online-algorithms and metric-driven problems. It is well motivated, and builds upon interesting known ideas in a novel way. The introduction of the \"push-relable\" subroutine instead of augmenting paths, as well as the careful analysis of the \"Find-Admissable-Edge\" subroutine allow a clean generalization of the static algorithm. The authors present these deviations well, which contributes to the merit of the paper. The analysis is relatively straightforward, but the ideas are non trivial.", "weaknesses": "The paper does not stress in the main body where the assumption of Metricity is necessary, only in the analysis. Since this assumption is critical - a mention is in need.\nThe experiments need a little more content. The synthetic data analysis seems to be missing (or I have missed it). More importantly, the authors stress that this algorithm is not restricted to the assumption of a Euclidean metric. A comparison with a synthetic dataset that is not Euclidean would be interesting, and will support the strengths of the paper as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FP5giHwEuv", "reviewer": "Reviewer_HS5c", "summary": "The paper considers the \\emph{metric bipartite matching problem} in the incremental setting: given two sets of points in a metric space undergoing insertions, the goal is to maintain a minimum-cost matching of one set to the other, where the cost is measured in terms of distances in the metric space, while minimizing the time spent updating the output. The authors present an algorithm achieving an $O(1/\\delta^{\\sim 0.631})$-approximation to the problem with $\\tilde{O}(n^{1+\\delta})$ update time.\n\nThe only comparable result is that of Goranci et al. (ICML'25), who obtain an $O(1/\\epsilon)$-approximation for the problem with $\\tilde{O}(n^{O(\\epsilon)})$ update time under both point insertions and deletions. However, their algorithm is restricted to low-dimensional Euclidean metrics. Minimum-cost bipartite matching is much more challenging in general metrics, even in the static setting. The result presented by the authors is, to the best of my knowledge, the first algorithm addressing the problem in the dynamic setting for general metrics.\n\nThe algorithm presented by the authors closely follows that of Agarwal and Sharathkumar (STOC'14), which achieves the same approximation ratio for the static problem in $O(n^{2+\\delta})$ running time (roughly equivalent to the total running time of the algorithm presented by the authors over the entire insertion sequence). The algorithm of Agarwal and Sharathkumar, in turn, builds on the influential work of Gabow and Tarjan (SIAM), who developed a scaling algorithm for exact minimum-cost bipartite perfect matching in graphs, running in $\\tilde{O}(n^{2.5})$ time and based on augmenting path elimination techniques. At a high level, Agarwal and Sharathkumar modify this algorithm by approximately completing its scaling steps, resulting in an approximate solution with an almost $n^2$ running time.\n\nThe algorithm presented by the authors can be viewed as an incremental implementation of that of Agarwal and Sharathkumar. A crucial challenge in this approach is that the underlying algorithm relies on augmenting path elimination techniques, which are difficult to implement in the dynamic setting, even for maximum cardinality graph matching, when the cost of the optimal solution does not evolve monotonically, as is the case in Euclidean matching. The main technical contribution of the paper lies in overcoming this challenge by formalizing the algorithms of Agarwal and Sharathkumar (and Gabow and Tarjan) as a push-relabel framework, which naturally adapts to the dynamic setting.\n\nThe authors also present experiments comparing the performance of their algorithm to greedy and quad-tree-based implementations (Sariel Har-Peled) with respect to Euclidean norms on the MNIST, NYC-TAXI, and synthetic datasets. The results show predictable behaviour in terms of approximation: the algorithm proposed in the paper outperforms both the greedy and quad-tree-based implementations (although it is unclear how it compares to the optimal solution). In terms of update time, the batch-update variant of the proposed algorithm significantly outperforms the greedy approach and slightly underperforms the quad-tree-based implementation.\n\nOverall, I consider the paper to be an important contribution to the study of the widely applied metric minimum-cost bipartite matching problem in the dynamic setting, which has recently received growing attention, due to being the first paper considering the problem in general metrics.", "questions": "My questions would concern the performance of the algorithm for the test cases described in the weaknesses section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The formulation of a variant of the Agarwal and Sharathkumar (and Gabow and Tarjan) algorithm as a push-relabel framework is interesting and, I suspect, will be of independent research interest.", "weaknesses": "The algorithm (in contrast to that of Goranci \\emph{et al.}) is designed to handle only point insertions. This is somewhat surprising. While for most problems the incremental and decremental settings have proven to be simpler than the fully dynamic one, one might expect this not to be the case for metric minimum-cost matching, as the objective value evolves non-monotonically under partially dynamic updates.\n\nIn terms of experimental results, a comparison to the work of Goranci \\emph{et al.} would be interesting to see. Based on the theoretical guarantees, with the same slack parameter, one would expect the latter to be more time-efficient at the cost of some loss in approximation ratio relative to the algorithm proposed in this paper. However, since quad-tree-based techniques (such as those of Goranci \\emph{et al.}) tend to perform better in practice than in theory, it would be important to see that (at least on low-dimensional Euclidean datasets) the algorithm presented in this paper strictly outperforms the previous approach in at least one aspect.\n\nFurthermore, an experiment not restricted to Euclidean distances (preferably on non-synthetic data) would intuitively should demonstrate a significant improvement over the greedy algorithm in terms of approximation ratio.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3oAYIyoAGU", "reviewer": "Reviewer_DQGv", "summary": "This paper studies the bipartite matching problem for general metrics in the incremental setting. Specifically, given a fixed point set $S$ and an initially empty point set $R$, the goal is to maintain a matching between $S$ and the current $R$ as new points are incrementally inserted into $R$. The paper presents an algorithm that maintains an $O(1/\\delta^{0.631})$-approximate minimum-cost matching in amortized time $O(n^{1+\\delta})$, ignoring lower-order terms and assuming that the aspect ratio of the underlying metric space is polynomially bounded.\n\nIn the static setting, this problem closely relates to estimating the discrete 1-Wasserstein distance, a fundamental quantity in optimization, applied mathematics, machine learning, and theoretical computer science. It has been extensively studied across many computational models. The dynamic (or incremental) setting considered here—where the underlying point sets evolve over time—is both practically motivated and theoretically rich. The only prior work in this area is by Goranci et al.~(ICML'25), which addresses the more general fully dynamic case (supporting both insertions and deletions) but is restricted to low-dimensional Euclidean metrics.\n\n*Technical Contribution*: The central idea builds on the static approximation algorithm of Agarwal and Sharathkumar~(STOC'14) (derived from the classical Gabow--Tarjan framework). However, it is far from obvious how to \\emph{dynamize} that algorithm, even in the incremental setting. Skipping many standard details, the paper’s main novelty lies in replacing the traditional *augmenting-path* step with a *push--relabel* step. While individual point insertions may still be expensive in the worst case, the push--relabel mechanism enables strong amortized guarantees. In hindsight, this is a particularly elegant and insightful design choice. This contribution alone, in my view, justifies acceptance at ICLR.\n\nLast but not least, the paper demonstrates that the conceptual simplicity of the proposed approach translates into competitive empirical performance on both real-world and synthetic datasets.", "questions": "-- The algorithm by Goranci et al. 2025 does work for arbitrary point insertions and deletions, and it's not restricted to pairs of point insertions or deletions (even though it's not explicitly stated); so claiming that as a weakness doesn't seem appropriate.\n\n-- In related works, the paper says that adapting recent breakthrough fast max-flow techniques in the incremental setting seems challenging; however, this has been done: https://arxiv.org/pdf/2311.03174 in the approximate setting (and the paper under review also works in the approximate regime); it still doesn't solve the problem considered in the paper, but some discussion would be due here.\n\n-- Can you explain why you decided to consider only Euclidean data sets in the experiments?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "-- The paper studies a central problem that lies at the intersection of several fields, and is highly relevant to modern machine learning, especially in the context of emerging computational models.\n\n-- The use of push–relabel techniques to design incremental algorithms, in contrast to the traditional approach of searching for augmenting paths, represents the most novel and technically interesting aspect of the paper.\n\n-- The presentation is generally clear and well-organized, with sufficient intuition and explanation provided beyond the core algorithmic details.", "weaknesses": "-- I would expect some better discussion of state-of-the-art resutls on this space (see my comments below:)\n-- The result is advertised as applying to general metrics. However, the experiments involve Euclidean data sets. I would expect a bit more effort on this aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3F5y7WtrGL", "reviewer": "Reviewer_V2JC", "summary": "This paper focuses on the incremental metric bipartite matching problem, where a fixed set of servers S (in a metric space) needs to be dynamically matched to incrementally arriving requests R. The core challenge it addresses is maintaining an approximate minimum-cost matching with efficient update times.", "questions": "Your guess-and-double trick requires reprocessing all historical requests when ω  is doubled. For large n (e.g., 100k requests), this could add significant runtime. How many such resets occur in practice for your real-world datasets (MNIST, NYC-Taxi)?\n\nYour GPU implementation is mentioned but not detailed. Which submodules (e.g., distance matrix computation, admissible edge search, slack updates) are parallelized? What speedup do you see over the CPU implementation for each submodule, and is a batch size of 200 optimal (or would larger batches improve GPU utilization)?\n\nLogistics scenarios often have bursty request arrivals (e.g., rush hour for taxis). How does your algorithm handle queue buildup under bursty arrivals? Does batch parallelism mitigate this?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "It breaks a key barrier of prior incremental matching algorithms by supporting arbitrary metric spaces, which is a critical generalization for applications like high-dimensional ML (e.g., dynamic alignment of MRI scans) and unbalanced logistics. The push-relabel framework is a clever adaptation: replacing augmenting paths with local push/relabel steps reduces per-insertion overhead, making the algorithm feasible for large-scale systems.\n\nThe theoretical analysis is comprehensive. The results are not just theoretical, since practical versions are optimized for real-world use, with batch processing that leverages parallelism to handle high-throughput requests.", "weaknesses": "The main problem is the experiment design. The authors fix server size and delta. And, logistics scenarios require unbalanced R and S, but in the experiments, |S| = |R|. \n\nOne crucial invariant of the algorithm is that a server that is matched at any level 0 ≤ i ≤ µ is only available to requests that are at level i or higher, but this is under-motivated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)