Source-linked AI summary
Better bounds for matchings in the streaming model
Michael Kapralov
TL;DR
The paper studies how well maximum matching can be approximated in bipartite-graph streams with limited space and few passes. It proves a tight one-pass barrier for vertex arrivals and gives improved multipass results.
Problem
The paper addresses the limited-space approximation of maximum matching in streaming models, including vertex and edge arrivals.
Method
The paper combines hard input distributions and communication-style lower bounds with a simple multipass algorithm for vertex arrivals.
Results
No one-pass algorithm using near-linear space can achieve better than 1−1/e for vertex arrivals, while the paper also improves multipass approximation results and the edge-arrival impossibility bound.
Takeaways & Limitations
With near-linear space, single-pass streaming cannot outperform the corresponding online matching guarantee, whereas additional passes improve approximation in the vertex-arrival model.
Takeaways & Limitations
The analysis relies on parameter-setting assumptions and, in part, considers the YES case where the transformed graph has a perfect matching on one side.
Abstract
from arXiv · showhide
In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input using $\tilde O(n)$ space, where $n$ is the number of vertices in the input graph. Two natural variants of this problem have been considered in the literature: (1) the edge arrival setting, where edges arrive in the stream and (2) the vertex arrival setting, where vertices on one side of the graph arrive in the stream together with all their incident edges. The latter setting has also been studied extensively in the context of online algorithms, where each arriving vertex has to either be matched irrevocably or discarded upon arrival. In the online setting, the celebrated algorithm of Karp-Vazirani-Vazirani achieves a $1-1/e$ approximation. Despite the fact that the streaming model is less restrictive in that the algorithm is not constrained to match vertices irrevocably upon arrival, the best known approximation in the streaming model with vertex arrivals and $\tilde O(n)$ space is the same factor of $1-1/e$. We show that no single pass streaming algorithm that uses $\tilde O(n)$ space can achieve a better than $1-1/e$ approximation to maximum matching, even in the vertex arrival setting. This leads to the striking conclusion that no single pass streaming algorithm can do better than online algorithms unless it uses significantly more than $\tilde O(n)$ space. Additionally, our bound yields the best known impossibility result for approximating matchings in the edge arrival model. We also give a simple algorithm that achieves approximation ratio $1-e^{-k}k^{k-1}/(k-1)!=1-\frac1{\sqrt{2πk}}+o(1/k)$ in $k$ passes in the vertex arrival model using linear space, improving upon previously best known convergence.
1 Introduction
The paper establishes tight single-pass limits for maximum matching with near-linear space and improves multi-pass approximation in the vertex-arrival model. It also gives an efficient algorithm for the Gap-Existence problem.
- Lower bounds: 1−1/e is an optimal single-pass approximation for maximum matching with ˜O(n) space in the vertex-arrival setting.No possibly randomized algorithm can achieve 1−1/e+c with probability at least 3/4 unless it uses n^(1+Ω_c(1/log log n)) space.
- Lower bounds: The lower bound matches both the randomized KVV online algorithm and the deterministic ˜O(n)-space streaming algorithm.Thus, single-pass streaming cannot improve on the more constrained online setting without significantly more space.
- Lower bounds: The same result improves the best known small-space impossibility bound in the edge-arrival model beyond 2/3.Earlier work established a 2/3 lower bound for edge arrivals and a 3/4 lower bound for vertex arrivals.
- Multipass algorithms: 1−e^−k k^(k−1)/(k−1)! = 1−1/√(2πk)+O(k^−3/2) is achieved in k passes using linear space.The algorithm is based on fractional load balancing and runs in nearly linear time per pass.
- Gap-Existence: Gap-Existence can be solved in O(log(1/ε)∑_{a∈A} B_a/ε) time, with each pass nearly linear in the graph representation.This improves a prior sampling-based result that was sublinear when all budgets were large.
2 A toy construction
The toy construction creates hard bipartite matching instances in stages, where graphs contain nearly perfect matchings but small-memory single-pass algorithms cannot retain enough useful edges. Its analysis yields the approximation barrier 1−(1−1/k)^k for k-stage inputs.
- Construction: The T-side vertices are vectors in [m]^n, while S-side vertices are organized into stages and coordinate blocks.The coordinate partition [n] = B1∪⋯∪Bk parameterizes the graph family, and Ti contains vectors satisfying threshold constraints on selected coordinates.
- Construction: Each Si is a rate-1/k subsampling of Ti, with independent Bernoulli variables used to define additional subsets for the hard instance.Chernoff bounds and union bounds provide simultaneous concentration of the relevant set sizes and degrees.
- Hard input distribution: The stream reveals the stage subgraphs in arbitrary order and then adds a perfect matching from Tk to fresh vertices, while the algorithm retains only o(N log N) edges.Randomly selected coordinates determine the stages, and the memory restriction prevents retaining enough edges across all stages.
- Analysis: The stored-edge restriction combines with the large matching in the input graph to force the algorithm's approximation ratio toward 1−(1−1/k)^k.The relevant bounds hold with high probability, including probability at least 99/100 in the stated theorem and at least 98/100 after the construction events are accounted for.
- Hard input distribution: 1−(1−1/k)^k + δ is an upper bound on the approximation ratio for algorithms storing o(N log N) edges.The hard distribution exists for every k ≥ 2 and every δ ∈ (0, 1).
- Input family: The construction samples graphs with nearly perfect matchings, so the lower bound is not caused by a lack of an adequate matching.With suitable parameters, every graph in the relevant family contains a matching of size at least (1−δ/10)N.
3 Single pass streaming lower bound
The single-pass lower-bound construction replaces coordinate directions with an exponential-size family of nearly orthogonal vectors. This yields a space lower bound of n^(1+Ω(1/log log n)) for improving on the 1−1/e approximation.
- Lower bound: n^(1+Ω(1/log log n)) space is required to obtain a better than 1−1/e approximation in a single pass.The construction is designed for the streaming problem of approximating maximum matchings.
- Construction: The construction uses an exponential-size family of nearly orthogonal vectors instead of coordinate directions.The approach is inspired by techniques for constructing Ruzsa-Szemerédi graphs and their extensions.
3.1 Construction of host graphs G(u1, . . . , uk)
The host graphs are built from large families of equal-weight, nearly orthogonal binary vectors, randomized shifts, and nested vertex sets defined by modular dot-product constraints. These ingredients yield controlled set sizes and large matchings under suitable parameter conditions.
- Vector families: The construction uses vector families F_j whose vectors have equal Hamming weight w and pairwise dot products below ϵw.A family of size 2^Ω(ϵ^2m) exists, with w = (ϵ/2)m in the stated lemma.
- Randomized classification: Random shifts U_u are independently sampled from a discrete grid, while dot products and modular intervals define the graph’s vertex classes.The parameter W is chosen as a polynomial-scale multiple of the common Hamming weight, and η separates red, white, and blue regions.
- Ground sets: The ground sets are X* = Y = [m^4]^m, with X formed by independently retaining each point with probability 1/k.The host graph first selects a tuple (u_1, ..., u_k) from F_1 × ... × F_k.
- Nested sets: Nested sets T_i and S_i retain points satisfying blue-region constraints for the first i vectors, with T_0 = Y and S_0 = X.Further sets impose additional constraints on later vectors, creating the layered structure used by the host graph.
- Graph structure: The bipartite graph has T = T_0 and a disjoint-union S = S_0 ∪ ... ∪ S_k, with total size O(n) when n = |T|.The construction labels vertices by hypercube points, while labels may repeat across different S_i layers.
- Size and matching guarantees: With probability at least 99/100, the layered sets have controlled sizes, including |T_i| = (1 − 1/k)^i|Y| + Δ_i with |Δ_i| = O(k^3ϵ/θ)|Y|.Under these conditions, large matchings cover a 1 − O(k^3ϵ/η) fraction of S_i, and the fractional matching has size (1 − O(ηk))|S_i|.
3.2 Distribution over inputs
The hard input distribution samples a host graph, subsamples edges through independent Bernoulli choices, and reveals the resulting graph in k + 1 vertex-arrival phases. With high probability, the sampled graph still contains a nearly large matching.
- Distribution construction: The input graph G′ is generated by sampling X, choosing vector parameters, and then sampling independent random shifts and vectors for the host graph.The resulting host graph is indexed by a tuple (u_1, ..., u_k) and subsequently modified by edge subsampling.
- Edge subsampling: For each phase layer, Bernoulli variables retain all edges incident on selected vertices with probability 1 − ξ and delete them otherwise.For the final layer S_k, all incident edges are included rather than subsampled.
- Streaming order: The stream has k + 1 phases, with vertices and incident edges from S_i arriving in phase i in arbitrary order.The phases range from i = 0 through k, matching the layered construction of the host graph.
- High-probability guarantee: Under the stated parameter restrictions, a large-matching event occurs with probability at least 97/100 over the random shifts.The event combines balanced-degree and per-layer success events through a union bound.
- Layered matchings: Conditioned on the relevant events, each intermediate layer has a matching covering a 1 − O(k^3ϵ^1/2/η) fraction of S_i, while S_k can be perfectly matched to T_k.Taking the union of these layer matchings yields a large matching in the sampled graph.
3.3 Bounding performance of a small space algorithm
The proof bounds the matching output by a small-space one-pass algorithm and uses information theory to show that exceeding the target approximation requires superlinear space.
- Information-theoretic reduction: Yao’s minimax principle reduces the analysis to deterministic algorithms succeeding with probability at least 1/2.The proof then studies the matching MALG produced after one pass.
- Performance upper bound: |MALG| ≤ (1 −1/k)^k|Y | plus an additional term bounds every matching in the constructed graph.This upper bound is obtained through a maxflow/mincut argument and the canonical decomposition.
- Information lower bound: The proof lower-bounds information about the hidden subsampling variable Bi from the algorithm’s output using the data processing inequality.The argument obtains I(Bi : Π) ≥ Ωk(c) · d^n and converts this information requirement into a space lower bound.
- Conclusion: s = Ωc,k(nd) = n1+Ωc(1/ log log n), ruling out a (1−1/e+c)-approximation in one pass with near-linear space.The theorem’s contradiction is instantiated by choosing k so that the target exceeds 1−(1−1/k)^k by a constant margin.
- Hard-instance completeness: The constructed graph contains a large matching with probability at least 97/100, forcing any successful algorithm to output a matching above the upper-bound threshold.Parameter choices make the approximation loss terms small relative to the constant gap c.
4 Multipass approximation for matchings
The paper gives a water-filling algorithm for vertex-arrival streams and analyzes its matching quality over multiple passes. Its guarantee improves with the number of passes according to a Gamma-distribution expression.
- Algorithm: The algorithm maintains a fractional matching by assigning each arriving vertex’s unit of water to least-loaded neighbors.After k passes, it truncates overloaded right-side vertices, scales by 1/k, and rounds to a matching.
- One pass: 1−1/e is the one-pass approximation ratio obtained by the water-filling analysis.The proof uses the distribution of vertex levels after the first pass.
- Multiple passes: 1−e^-k k^(k−1)/k! is the approximation ratio after k passes under the perfect-matching analysis.The bound follows from the Gamma distribution governing the level-set recurrence.
- General case: The general-graph analysis uses canonical decomposition, vertex capacities, and reweighted level sets to extend the guarantee beyond perfect-matchable graphs.The canonical matching is maximum, and the proof bounds the relevant level-set integral using this structure.
- Guarantee: 1−e^-k k^(k−1)/(k−1)! is the stated k-pass approximation guarantee for maximum matching.The paper presents this as the main multipass result, with an asymptotic convergence characterization in the surrounding analysis.
5 Gap-existence
The paper develops a discretized water-filling procedure for Gap-existence that uses a bounded active-neighbor set. In the YES case, it certifies a near-feasible matching while controlling space and overflow.
- Algorithm and space: The Gap-existence algorithm maintains only O(|A|/ǫ) active vertices while using an oracle to discover new neighbors.DISCRETIZEDWATERFILLING explicitly maintains I* of this size.
- Decision rule: The algorithm outputs YES when at most ǫ/2 water lies above level k/(1−ǫ/2).This threshold tests whether the allocation has sufficiently little high-level overflow.
- Correctness: In the YES case, the algorithm finds a matching with budgets ⌊(1−ǫ)Ba⌋ for every advertiser a.The proof scales the allocation, truncates water above level k, and divides by k.
- Conclusion: The proof concludes that the discretized procedure completes the Gap-existence guarantee under the stated parameter conditions.The construction replaces advertiser budgets by unit-demand copies and assumes a perfect matching in the resulting graph for the YES-case analysis.
- Analysis: The level-set analysis bounds water above the truncation threshold using inductive differential inequalities and exponential-distribution integrals.The argument compares the actual level-set function with a function satisfying a differential equation.
A Proofs omitted from Section 3
The omitted proofs establish the combinatorial and geometric properties needed by the hard instance, including discretization shifts and the small fraction of boundary vertices.
- Discretization: The hard-instance construction uses the cube Y = [m^4]^m and discretizes it according to constraints on vector dot products.The discretization partitions points using shifted modular intervals indexed by binary vectors.
- Bad vertices: Bad vertices are cube points with at least one coordinate below m^2 or above m^4−m^2.These boundary points are excluded from the clean shift arguments.
- Bad-vertex bound: |B| ≤ (2/m)|Y |, so the bad-vertex set is a small fraction of the cube.The bound follows from a union bound over coordinates.
- Shifting map: The shifting map moves points between discretization cells while preserving the relevant modular constraints up to controlled error.The error is bounded using equal Hamming weights and near-orthogonality assumptions.
- Cell-size estimates: The shifting and discretization lemmas provide matching lower and upper bounds on cell sizes by relating cells through injective maps.These bounds are combined to establish the required size estimates for the constructed sets.