betaFeedback

WorksComputer Science

Matching in Random-Order Streams via Historical Deletion Bounds

Abstract

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed ε>0\varepsilon>0, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of 0.712950.71295 for unweighted graphs and 0.71295−ε0.71295-\varepsilon for weighted graphs, using near-linear space with an explicit charge for weight precision. Both approximation ratios hold for bipartite and general graphs. The algorithm does not require the stream length or the weight range in advance. The main structural ingredient is a historical deletion inequality for weighted matchings. The deletion price of a vertex set is the decrease in maximum matching weight when that set is removed. We bound the sum of these prices for pairwise disjoint vertex sets, even when each price is evaluated at a different stage as edges are added to the graph. Applied to the usual unfolding of integer weights, it transfers a bipartite cardinality certificate to an original weighted matching, even when the original graph is not bipartite. This transfer preserves the approximation coefficient. We combine this transfer with a refined analysis of fractional matchings in the two auxiliary graphs arising in the transfer theorem. An exact rational linear-programming certificate proves the stated constant for every feasible graph profile. The approximation guarantees and the new structural results are formally verified in Lean.

Introduction

In the random-order streaming model, the edges of a fixed graph arrive in a uniformly random permutation. We seek a large matching after one pass, using memory near-linear in the number of vertices. The input graph is otherwise arbitrary.

For maximum cardinality matching, Bernstein obtained a (2/3−ε)(2/3 - \varepsilon)-approximation in one pass using Oε(nlog⁡2n)O_{\varepsilon}(n \log^{2} n) bits [5]. Assadi and Behnezhad subsequently crossed the 2/32/3 threshold, obtaining a (2/3+ε0)(2/3 + \varepsilon_{0})-approximation for an absolute constant ε0>0\varepsilon_{0} > 0, with an explicit improvement of approximately 10−1410^{-14} [2]. For maximum weight matching, Hashemi and Wrzos-Kaminska obtained a (2/3−ε)(2/3 - \varepsilon)-approximation [13]. All three guarantees hold for both bipartite and general graphs.

The weighted algorithm of Hashemi and Wrzos-Kaminska builds on Bernstein’s approach using an unfolding of integer weights. An original edge of weight ww produces ww unweighted edges between copies of its endpoints; we call the original edge the parent of each resulting copied edge. These copies arrive together as a batch when their parent arrives, so the resulting stream is not a uniformly random permutation of the copied edges.

Refolding a set of copied edges means returning to the original weighted subgraph formed by their parents. Even when the selected copies form a matching, their parents may share vertices. In a general graph, the refolded subgraph need not contain a matching whose weight is as large as the number of selected copies. Hashemi and Wrzos-Kaminska’s analysis handles both the correlations within arriving batches and this refolding difficulty while preserving the 2/3−ε2/3-\varepsilon guarantee [13]. Our improvement combines a stronger bipartite cardinality certificate with a historical transfer theorem that carries this certificate to weighted general graphs without reducing the approximation coefficient.

For any fixed ε>0\varepsilon> 0, we obtain a 0.71295-approximation for unweighted matching and a (0.71295−ε)(0.71295-\varepsilon)-approximation for weighted matching. Both guarantees hold for bipartite and general graphs.

Theorem 1.1 (Main result). Let n≥2n \ge2, and let GG be a simple graph on a known vertex universe of size at most nn, whose edges arrive in a uniformly random order. For every 0<δ<10 < \delta< 1, put Λ=1+log⁡(n/δ)\Lambda= 1 + \log(n/\delta). There is a deterministic one-pass algorithm that returns a matching of size at least 0.71295 ν(G)0.71295\,\nu(G) with probability at least 1−δ1-\delta over the arrival order, using O(nΛ6)O(n\Lambda^6) bits, where ν(G)\nu(G) is the maximum matching size.

For every fixed 0<ε<10 < \varepsilon< 1, a deterministic one-pass algorithm for positive rational edge weights returns a matching of weight at least

(0.71295−ε)OPT⁡w(G)(0.71295-\varepsilon)\operatorname{OPT}_{w}(G)

with probability at least 1−δ1-\delta over the arrival order, where OPT⁡w(G)\operatorname{OPT}_{w}(G) is the maximum matching weight. It uses

Oε(nΛ6(Bwt+Λ))O_{\varepsilon}\bigl(n\Lambda^{6}(B_{\mathrm{wt}}+\Lambda)\bigr)

bits, where BwtB_{\mathrm{wt}} bounds the binary length of each input numerator and denominator. Neither algorithm requires the stream length in advance; the weighted algorithm also does not require the weight range. Running time is polynomial in the encoded input size for fixed ε\varepsilon.

Table 1 summarizes the previous and new approximation guarantees in all four settings. All entries return a matching in one random-order pass. The previous unweighted bound uses O(nlog⁡2n)O(n\log^2 n) bits when the stream length is known; geometric guesses remove that assumption at an additional logarithmic cost. In the same bit accounting, the previous weighted algorithm uses Oε(nlog⁡n(1+log⁡R)(Bwt+log⁡n))O_{\varepsilon}(n\log n(1+\log R)(B_{\mathrm{wt}}+\log n)) bits, where RR is the ratio of the largest to the smallest edge weight. Our storage bound has no separate dependence on RR; it still charges the encoded precision of the weights. In particular, O(log⁡n)O(\log n)-bit weights and inverse-polynomial failure probability give Oε(nlog⁡7n)O_{\varepsilon}(n\log^7 n) bits. The constants in our space bound are large.

SettingPrevious one-pass guaranteeThis paper
Unweighted bipartite2/3+ε02/3+\varepsilon_00.71295
Unweighted general2/3+ε02/3+\varepsilon_00.71295
Weighted bipartite2/3−ε2/3-\varepsilon0.71295−ε0.71295-\varepsilon
Weighted general2/3−ε2/3-\varepsilon0.71295−ε0.71295-\varepsilon

Table 1. Approximation guarantees for one-pass matching in random-order streams. Previous guarantees are due to Assadi and Behnezhad [2] for unweighted matching and Hashemi and Wrzos-Kaminska [13] for weighted matching.

Assadi and Behnezhad showed that, even for unweighted bipartite graphs, achieving a (1−ηn)(1-\eta_n)-approximation in one random-order pass requires n1+Ω(1/log⁡log⁡n)n^{1+\Omega(1/\log\log n)} space for some ηn=Θ(1/log⁡n)\eta_n=\Theta(1/\log n) [2]. This leaves open how far constant-factor approximation can be improved in near-linear space. For adversarial edge order, Assadi, Jiang, and Xiang proved that no one-pass semi-streaming algorithm can achieve any constant approximation ratio greater than 1/2 with constant success probability, even for unweighted bipartite graphs [3].

A transfer theorem for weighted general graphs. For a weighted graph KK, define the deletion price of a vertex set XX by

DK(X)=OPT⁡w(K)−OPT⁡w(K−X).D_K(X) = \operatorname{OPT}_w(K) - \operatorname{OPT}_w(K-X).

This measures the loss in maximum matching weight caused by deleting XX. Suppose K0⊆⋯⊆KmK_0 \subseteq\cdots\subseteq K_m is an increasing sequence of graphs with fixed edge weights. Our structural theorem bounds the sum of deletion prices of pairwise disjoint vertex sets, even when each price is measured in a different graph in the sequence. Its proof uses a submodular potential defined by pairs of matchings with marked vertices. A weighted Tutte matrix supplies the submodularity.

Consider a phase that maintains a graph KK and stores an arriving edge precisely when adding it increases the maximum matching weight. Immediately after each test, adding the tested edge cannot increase the optimum: a stored edge is already present, and a rejected edge did not improve it. Thus, for a tested edge uvuv and the graph KK immediately after its test,

w(uv)≤DK({u,v}).w(uv) \le D_K(\{u,v\}).

This inequality need not remain valid as KK grows, because an edge rejected earlier can become useful after later insertions. The historical theorem lets us bound the sum of deletion prices for disjoint vertex sets while evaluating each price at the relevant test time.

To apply the historical inequality to unfolded edges, we must handle matchings of copies whose original parents may share vertices. An auxiliary bipartite graph and integral matching duality resolve this difficulty. The resulting theorem transfers a cardinality certificate on copied graphs to a weighted matching guarantee in the original general graph, without reducing the approximation coefficient. The copied graphs cross a fixed cut used only in the proof. Thus one certificate suffices for all four settings in Table 1. The transfer requires support whose parents are present at the start of a phase and selected copies whose parents are initially present or tested later. It is therefore not a reduction from an arbitrary unweighted streaming algorithm.

A stronger repair certificate. The algorithm first acquires a sparse reference graph in the unfolding and subsequently stores copies whose endpoint-degree sum in that reference is small. A bank of phases supplements this shared graph. To analyze one designated phase, fix a benchmark matching and a minimum vertex cover of the shared graph restricted to the analytic cut. If the shared graph has a small maximum matching, many benchmark edges have both endpoints outside the cover. Their endpoints have large combined reference degree, providing support for fractional matchings in the two vertex-deletion graphs of the transfer theorem. Benchmark edges that are available to the phase provide additional contributions.

The repair uses all vertices outside the cover. Their contributions to the two deletion matchings depend on their role in the benchmark matching. We record these roles and the reference degrees in a degree profile, including benchmark edges with both endpoints in the cover. After grouping vertices by degree interval, every graph arising in this analysis gives a feasible solution to a finite linear program. An exact rational dual certificate proves that the shared-graph and repair bounds cannot both be below 0.7129530279 . . . times the benchmark value. After accounting for concentration error and the acquisition prefix, the ratio remains above 0.71295.

Related techniques. Early improvements over greedy matching in random-order streams use augmentation and careful exposure of the stream [15, 8]. Our reference construction belongs to the line of degree-constrained matching sparsifiers developed in [6, 1] and used for random-order matching by Bernstein [5]. Graph unfolding originates with Kao, Lam, Sung, and Ting [14]; its use for streaming matching was developed in [4, 13]. We use standard separated weight bands and greedy combination to remove the weight range, while discarding only entire local instances [11, 7]. The algebraic representation uses the weighted even-factor identity attributed to Cunningham and Geelen by Kobayashi and Takazawa [16 Theorem 4.2]; our structural contribution is the deletion potential and its historical bound.

After the model and notation, section 3 presents the algorithm and proof overview. Sections 4 and 5 establish the historical transfer and the repair certificate. The appendices give the algebraic, probabilistic, and space details. The formal verification and AI methodology are described in section F.

Model and notation

All graphs are finite and simple. We write ν(G)\nu(G) for maximum matching cardinality and OPT⁡w(G)\operatorname{OPT}_{w}(G) for maximum matching weight, or OPT⁡(G)\operatorname{OPT}(G) when the weights are understood. A vertex deletion removes every edge incident to a deleted vertex. An algorithm returns an actual matching of input edges.

The random-order distribution is a uniform permutation of the original edges of a fixed input graph. A stream of batches is a uniform permutation of fixed, disjoint batches, each with at most κ\kappa edges; the order within each batch is fixed. Restriction to a fixed subset of original labels preserves uniform order. Edges belonging to one batch remain dependent throughout the analysis. The algorithms below are deterministic; their success probability is over the input permutation. Random cuts and repair choices are used only in the analysis.

Space is measured in bits. Original vertex identifiers use O(log⁡n)O(\log n) bits. For rational weights, BwtB_{\mathrm{wt}} denotes the largest binary length of an input numerator or denominator; it need not be known in advance. Our bounds include these weight encodings, as well as the stored edges, indices, counters, and temporary matching workspace.

For integer weights in [W][W], the canonical unfolding ϕ(G)\phi(G) has copies v1,…,vWv_1,\ldots,v_W of every original vertex. An original edge uvuv of weight ww produces the ww edges

uivw+1−i(1≤i≤w).u_i v_{w+1-i}\qquad(1 \le i \le w).

These edges arrive as one batch when their parent arrives. An original matching unfolds to a matching of cardinality equal to its weight. If GG is bipartite, the reverse optimum equality also holds. We will only use this reverse implication on graphs crossing a specified cut. For general graphs we use the historical transfer theorem instead.

Lemma 2.1 (Bipartite refolding). For a bipartite graph AA with integer weights in [W][W], ν(ϕ(A))=OPT⁡w(A)\nu(\phi(A))=\operatorname{OPT}_{w}(A). Consequently every partial copied matching supported on originals crossing one fixed original-vertex cut has cardinality at most the maximum matching weight of those originals.

Proof. Unfolding an original optimum proves one direction. Integral weighted bipartite matching duality supplies nonnegative integer vertex prices pvp_v with pu+pv≥wuvp_u+p_v \ge w_{uv} and ∑vpv=OPT⁡w(A)\sum_v p_v=\operatorname{OPT}_{w}(A); this is the standard assignment duality underlying the Hungarian method [17]. Take the bottom min⁡{pv,W}\min\{p_v,W\} copies of each vertex. If neither endpoint of a copied edge uivw+1−iu_i v_{w+1-i} were selected, then i>pui>p_u and w+1−i>pvw+1-i>p_v, implying w>pu+pvw>p_u+p_v, a contradiction. Thus these vertices cover ϕ(A)\phi(A) and their number is at most OPT⁡w(A)\operatorname{OPT}_w(A). Every copied matching is bounded by this cover size. The final assertion follows by restricting to the given cut and then to the partial copied support.

An edge ee is closed in KK if OPT⁡(K+e)=OPT⁡(K)\operatorname{OPT}(K+e)=\operatorname{OPT}(K). Every edge already present in KK is closed. For a cut (L,R)(L,R) and a crossing matching TT, let IL(T)I_L(T) and IR(T)I_R(T) denote its left and right endpoint sets. The same notation applies to copied matchings in the unfolded graph.

We use the exact constant

R∗=28963716759106947894062500000000000000,a∗=(R∗−10−7)(1−2⋅10−8)>0.71295.R_*=\frac{2896371675910694789}{4062500000000000000},\qquad a_*=(R_*-10^{-7})(1-2\cdot10^{-8})>0.71295.

The bounded-integer algorithm achieves a∗a_*. The arbitrary-weight reduction spends a separately chosen ε\varepsilon allowance.

Algorithm and proof overview

We first work with integer weights in [W][W]. There are two kinds of stored graphs: a sparse shared graph in the unfolding, and a bank of phase graphs on the original vertices. The shared graph supplies a baseline matching. Each phase supplements the part of that graph available at its start by retaining later edges with positive insertion gain. All matching computations in the phases use the original weights.

Acquisition and the phase bank

Acquiring a reference. Process each original arrival as its fixed batch of unfolded copies. The acquisition procedure maintains a copied reference HH: insert a copy uvuv if dH(u)+dH(v)<(1−λ0)β0d_H(u)+d_H(v)<(1-\lambda_0)\beta_0, and then delete edges whose endpoint-degree sum exceeds β0\beta_0 until the upper constraint is restored. A fixed tie rule makes these updates deterministic. Divide acquisition into epochs of original arrivals and freeze HH at the end of the first epoch with no insertion. Subsequent degree tests use this frozen reference.

The reason for an empty epoch is statistical. If many remaining originals contained an underfull copy, a uniformly ordered epoch would be unlikely to avoid all of them. Meanwhile, a bounded potential limits the number of epochs containing an insertion. These two facts let us freeze after a short prefix and store the subsequent underfull copies within a prescribed cap, except on a charged failure event. Theorems D.1 and D.2 give the potential and the conditional sampling argument.

The state after freezing. Write e1,…,eme_1,\ldots,e_m for the remaining original edges. Let U≤iU_{\le i} be the copied edges among their first ii batches that are underfull with respect to HH, and let par⁡(D)\operatorname{par}(D) denote the original parents of a copied edge set DD. The phase-bank procedure is as follows.

  1. On arrival eie_i, add its underfull copies to U≤iU_{\le i} and retain their original parent and timestamp. If this would exceed the prescribed cap, abort this local instance.

  1. For every phase already started at a cutoff c<ic<i, update its current original graph by

Kc←{Kc+ei,OPT⁡w(Kc+ei)>OPT⁡w(Kc),Kc,otherwise.K_c\leftarrow \begin{cases} K_c+e_i, & \operatorname{OPT}_w(K_c+e_i)>\operatorname{OPT}_w(K_c),\\ K_c, & \text{otherwise}. \end{cases}
  1. If ii is a scheduled cutoff, start a new phase with Ki=par⁡(H∪U≤i)K_i=\operatorname{par}(H\cup U_{\le i}).

  1. At the end of a nonaborted execution, return a maximum-weight matching in the union of the full shared parent graph par⁡(H∪U≤m)\operatorname{par}(H \cup U_{\le m}) and all final phase graphs.

Thus a later underfull edge is saved in the shared graph, while an existing phase applies the same insertion test to it as to every other arrival. A phase’s initial support contains only records available at its cutoff. This distinction matters in the transfer argument below.

Every tested edge is closed in its post-test host: an accepted edge is present, and a rejected edge has zero insertion gain. The host only grows, but an edge’s closure need not persist as it grows. We will use closure at the edge’s own test time. Each accepted edge raises the integral optimum by at least one, and that optimum is at most W⌊n/2⌋W\lfloor n/2\rfloor. Hence a phase adds at most this many original edges beyond its initialization. Exact matching calls are performed on the retained host; their running time and bit workspace are accounted for in section D.

Phase starts follow a geometric grid of reached suffix positions. The complete algorithm also runs acquisition instances for dyadic guesses of the input length, all from the beginning of the stream. At the end it uses the scale containing the actual length. Exact buffers handle short inputs and short suffixes; a fallback matching handles aborted instances. These rules make the procedure causal even when the length is unknown, and hard caps bound its space on every execution. Only one acquisition instance and one of its phases are needed for the approximation proof.

From a copied certificate to the returned matching

Fix an optimum original matching before exposing the stream. After acquisition, retain its suffix edges as the benchmark MM, and put μ=w(M)\mu= w(M). Its unfolded matching M=ϕ(M)\mathcal{M} = \phi(M) has exactly μ\mu edges. The prefix analysis will show that μ\mu is close to the input optimum.

An original-vertex cut used only for analysis. Choose a cut separating the endpoints of every edge of MM, and assign all copies of an original vertex to its side. Independent orientations of benchmark pairs, together with independent sides for unmatched vertices, show that such a cut can also approximately halve every reference degree. We fix one balanced cut after fixing the unordered suffix and the acquisition history. The existence argument uses the large reference-degree scale; the algorithm never computes the cut.

Let H′H', U′U' be the crossing parts of the full shared copied graphs, and put B=H′∪U′B = H' \cup U' and b=ν(B)b = \nu(B). The balanced cut preserves the reference upper-degree bounds and the lower-degree bounds on non-underfull benchmark copies, after rescaling the threshold. It also preserves every edge of M\mathcal{M}. Thus the benchmark loses no weight at this step. Bipartite refolding (theorem 2.1) gives a matching of weight at least bb among the retained original parents. If VV denotes the returned value, then V≥bV \ge b on a nonaborted execution.

The certificate supplied by one phase. For a designated cutoff cc, let A0A_0 be a copied graph across the analytic cut whose parents belong to the phase’s initial host. Let JJ be a copied matching across the same cut whose parents are either initially present or tested after cc. The historical copied transfer of theorem 4.4 gives

ν(A0−IL(J))+ν(A0−IR(J))+∣J∣2≤OPT⁡w(Kcfinal)≤V.(1)\frac{\nu(A_0-I_L(J))+\nu(A_0-I_R(J))+|J|}{2} \le\operatorname{OPT}_w(K_c^{\mathrm{final}}) \le V. \tag*{(1)}

The ordinary support A0A_0 must be present from the start. The selected edges JJ need only have a closure time along the phase. In particular, an available benchmark parent arriving by cutoff cc is initially present, and one arriving after cc is tested. Either case is valid, even if that later test rejects it. Several selected copies can share the same original parent and its closure time.

The two terms in (1) measure how much support survives deleting the selected left endpoints and deleting the selected right endpoints. Their average, together with ∣J∣/2|J|/2, is a lower bound on an original weighted optimum. This is the step that lets us analyze bipartite copied graphs while the algorithm runs on a general graph.

To lower-bound the deletion terms, take a minimum vertex cover CC of BB. If bb is already large, the shared base suffices. Otherwise many benchmark edges have both endpoints outside CC. Reference incidences at these endpoints provide fractional matching support after deletion. Available benchmark edges and other outside vertices provide further contributions. Section 5 constructs the two fractional matchings and records which contributions can coexist. Its finite degree-profile certificate bounds the better of the base and repair values for every feasible profile.

Using random order

Condition on a concrete ordered acquisition history ending at the freeze. The remaining original labels are uniformly ordered. This conditioning fixes the reference, the unordered underfull graph, the benchmark and the analytic cut. It includes no condition on future cap survival or on the success of a phase.

Represent this suffix order by independent uniform clocks on the original labels. Every copy inherits its parent’s clock. The repair uses two fixed thresholds α<ω\alpha< \omega, specified in section 5: early labels have clock at most α\alpha, and late labels have clock greater than ω\omega. It defines A0A_0 from the reference and early available benchmark gates described in section 5, and selects JJ from benchmark copies according to their availability and clock. For every clock outcome zz, define

References

  1. [1]Sepehr Assadi and Aaron Bernstein. Towards a Unified Theory of Sparsification for Matching Problems. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of OASIcs, pages 11:1–11:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.arxiv.org/abs/1811.02009
  2. [2]Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of LIPIcs, pages 19:1–19:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.arxiv.org/abs/2102.07011
  3. [3]Sepehr Assadi, Max Jiang, and Mars Xiang. Semi-Streaming Matching in a Single Pass II: Greedy is Optimal, 2026. arXiv preprint, version 2.arxiv.org/abs/2607.14656
  4. [4]Aaron Bernstein, Aditi Dudeja, and Zachary Langley. A Framework for Dynamic Matching in Weighted Graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 668–681. ACM, 2021.DOI
  5. [5]Aaron Bernstein. Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of LIPIcs, pages 12:1–12:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
  6. [6]Aaron Bernstein and Cliff Stein. Fully Dynamic Matching in Bipartite Graphs. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 167–179. Springer, 2015.arxiv.org/abs/1506.07076
  7. [7]Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. In 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of LIPIcs, pages 347–358. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2010.
  8. [8]Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. Approximate Maximum Matching in Random Streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1773–1785. SIAM, 2020.arxiv.org/abs/1912.10497
  9. [9]Harold N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–443. SIAM, 1990.DOI
  10. [10]Harold N. Gabow. Data Structures for Weighted Matching and Extensions to b-matching and f-factors, 2016. Expanded version of SODA 1990 and STOC 1983 papers.arxiv.org/abs/1611.07541
  11. [11]Manoj Gupta and Richard Peng. Fully Dynamic (1 + ε)-Approximate Matchings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 548–557. IEEE, 2013.arxiv.org/abs/1304.0378
  12. [12]Mohsen Ghaffari and David Wajc. Simplified and Space-Optimal Semi-Streaming (2 + ε)-Approximate Matching. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of OASIcs, pages 13:1–13:8. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.
  13. [13]Diba Hashemi and Weronika Wrzos-Kaminska. Weighted Matching in the Random-Order Streaming and Robust Communication Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), volume 317 of LIPIcs, pages 16:1–16:26. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.arxiv.org/abs/2408.15434
  14. [14]Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, and Hing-Fung Ting. A Decomposition Theorem for Maximum Weight Bipartite Matchings. SIAM Journal on Computing, 31(1):18–26, 2001.DOI
  15. [15]Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum Matching in Semi-Streaming with Few Passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 7408 of Lecture Notes in Computer Science, pages 231–242. Springer, 2012.arxiv.org/abs/1112.0184
  16. [16]Yusuke Kobayashi and Kenjiro Takazawa. Even Factors, Jump Systems, and Discrete Convexity. Technical Report METR2007-36, Department of Mathematical Informatics, University of Tokyo, 2007. Journal version: Journal of Combinatorial Theory, Series B, 99(1):139–161, 2009; doi:10.1016/j.jctb.2008.05.001.DOI
  17. [17]Harold W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955.
  18. [18]Taihei Oki and Tamás Schwarcz. Generalizing the Multiple Exchange Property for Matroid Bases, 2026. arXiv v3, revised 28 July 2026.arxiv.org/abs/2511.16021

Paper details

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

views · 10

downloads · 1

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents