CS Paper Radar

An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching

Yang P. Liu, Kheeran Naidu, Hoai-An Nguyen, Janani Sundaresan

cs.DS ·submitted 2026-10-27 03:32 UTC · v1
theory

Abstract

We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model. Specifically, we show that any algorithm that outputs an $(1-\varepsilon)$-approximation to maximum matching requires $Ω(\log(1/\varepsilon))$ passes for constant $\varepsilon \in (0,1)$. Prior to our result, such tradeoffs were proven only conditioned on a certain combinatorial assumption about the density of Ruzsa-Szemerédi graphs. The state-of-the-art unconditional lower bound rules out any approximation factor better than $(8/9)$ in two passes but leaves open the possibility of a $(1-\varepsilon)$-approximation for any $\varepsilon > 0$ even in three passes. We provide two different proofs of our result: the first proof uses the recent hierarchical-embedding framework of Assadi, Konrad, Naidu, and Sundaresan (STOC 2024) along with combinatorial constructions using Ruzsa-Szemerédi graphs. The second extends the two-level Ruzsa-Szemerédi hierarchy of Konrad and Naidu (SODA 2024) beyond two levels and proves the corresponding communication lower bound directly by induction, rather than through a reduction to Index.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.77
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26

Matching in Random-Order Streams via Historical Deletion Bounds

cs.DS ·2026-11-12 ·Alireza Farhadi, Mohammadtaghi Hajiaghayi, Mohammad Mahdavi
theory similarity 0.72
Abstract · 38 pages, including appendices

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed $\varepsilon>0$, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of $0.71295$ for unweighted graphs and $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.

0.41

Fluid Limits and Upper Bounds for Randomized Greedy Matching

cs.DS math.CO ·2026-10-31 ·Sayan Mukherjee
theory similarity 0.71
Abstract

The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings. MRG repeatedly picks a uniformly random unmatched vertex and matches it to a uniformly random unmatched neighbor, if one exists. Since 1991, the best upper bound on its approximation ratio has been $2/3$, given by the Bomb graphs of [Dyer and Frieze (1991)]. We improve this bound to $0.6569$ on general graphs and $0.6607$ on bipartite graphs. Our constructions consist of copies of small gadgets, with specified vertex classes joined completely. We track each algorithm by counting gadget copies with each possible configuration of remaining vertices. Wormald's differential equation method [Wormald (1995)] shows that these counts, scaled by the size parameter of the construction, converge to a deterministic trajectory known as the \textit{fluid limit}, which is described by ordinary differential equations. This fluid limit approximation holds while the relevant vertex classes have positive density, and so we devise a separate counting argument determines the contribution from the end of the run. Furthermore, we apply our framework to Random Decision Order (RDO), in which vertices are processed in uniformly random order and choose unmatched neighbors according to fixed adversarial preferences. On bipartite graphs, we determine the exact limiting ratio on the Double-Bomb family of [Tang-Wu-Zhang (2020)]. Its minimum is $31/48$, confirming their numerical estimate of about $0.646$.On general graphs, we improve their upper bound of $5/8$, given by the paw graph, to $0.5946$ on a new family. Finally, we give one possible explanation for why $2/3$ seemed to be optimal for MRG in the concluding remarks.

0.23

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.70
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.12

Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness

cs.DS ·2026-09-22 ·Arash Ahadi, Morteza Alimi, Sharareh Alipour, Shayan Tayefeh
similarity 0.68
Abstract

In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}<p\le2/7,\\ 1/p, & 2/7\le p\le2/3,\\ 1/[2(1-p)], & 2/3\le p\le7/8,\\ 4, & 7/8\le p<1. \end{cases} \] In particular, a factor-\(4\) approximation holds throughout the entire feasible cardinality range, the factor is at most \(7/2\) whenever \(0<k\le 6n/7\), and equals \(3/2\) at \(k=2n/3\). The algorithmic framework is based on optimal laminar cut packings, their weighted tree representations, exact-cardinality rounding, and tree dynamic programming.

0.13

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

cs.DS ·2026-09-22 ·Sara Ahmadian, Edith Cohen, Mohammad Roghani
benchmark similarity 0.68
Abstract

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

0.08

Stochastic Matching with Polynomial Degree

cs.DS ·2026-11-02 ·Soheil Behnezhad
hot direction similarity 0.68
Abstract

We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

0.23

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

cs.DS ·2026-11-01 ·Jiale Chen
similarity 0.68
Abstract · Abstract shortened due to arXiv requirements

We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.

0.16