Source-linked AI summary
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
Kook Jin Ahn, Sudipto Guha
TL;DR
The paper asks how to adapt broad linear-programming techniques to matching in semi-streaming graphs, where edges may arrive adversarially and space is limited. It develops primal–dual and matching techniques for this setting, reporting an approximation scheme for weighted matching, fewer passes for bipartite cardinality matching, and extensions to variants.
Problem
Broad techniques such as linear programming had not been adapted to semi-streaming graph processing, where matching algorithms must handle adversarially ordered edges with space proportional to the number of vertices.
Source: §1 · pp. 1–2Method
The paper develops primal–dual linear-programming techniques and matching oracles, including a bootstrap from semi-streaming maximal matching to near-optimal matching.
Source: §1 · pp. 2, 4, §3.2 · p. 9Results
The paper reports a (1−ε)-approximation scheme for bipartite maximum weighted matching, improved pass counts for bipartite maximum cardinality matching, and extensions to b-matching and general graphs.
Source: §1 · p. 2, §4.1 · p. 13Takeaways & Limitations
The techniques apply to matching variants, although the paper notes unappealing running times for its general-graph results.
Source: §1 · p. 2For the capacitated bipartite b-matching case, the method finds only a fractional solution, and its space requirement depends on c_ij and b_i.
Source: §6.1 · p. 24
Abstract
from arXiv · showhide
In this paper, we study linear programming based approaches to the maximum matching problem in the semi-streaming model. The semi-streaming model has gained attention as a model for processing massive graphs as the importance of such graphs has increased. This is a model where edges are streamed-in in an adversarial order and we are allowed a space proportional to the number of vertices in a graph. In recent years, there has been several new results in this semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. We present several techniques to adapt and optimize linear programming based approaches in the semi-streaming model with an application to the maximum matching problem. As a consequence, we improve (almost) all previous results on this problem, and also prove new results on interesting variants.
1 Introduction
The paper asks how to solve matching problems on massive graphs in a few passes and little extra space, including when edges cannot be stored. It adapts primal–dual linear programming techniques to semi-streaming matching and reports improved results for matching and related variants.
1 Introduction
- Massive or implicitly defined graphs may have edges generated by black-box transducers that are prohibitive to store, motivating graph algorithms that process edges without storing them.The paper connects this setting to in-place algorithms and multipass streaming.Source: §1 · pp. 1–2
- The semi-streaming model allows O(Cεn poly log n) space for m edges arriving in any order, including adversarial order, with a tradeoff among solution quality, space, and passes.The paper asks whether broad techniques can be adapted to this model.Source: §1 · p. 2
- The paper applies primal–dual linear programming to graph problems, using it to obtain a maximum weighted matching approximation scheme and improve pass counts for bipartite maximum cardinality matching.The approach also extends to b-matching and general graphs, though the general-graph results have unappealing running times.Source: §1 · p. 2
- A streaming separation oracle is difficult to implement because super-linearly many input-dependent conditions require random access, despite only n variables.The paper frames designing such an oracle as a central technical challenge.Source: §1 · p. 3
- Semi-streaming algorithms for maximal matching can be bootstrapped to achieve a near-optimal matching within a few iterations.The paper identifies this as an interesting contribution even without a space constraint.Source: §1 · p. 4
- Reducing multiplicative-weights passes requires recursively identifying small, critical subgraphs, while weighted variants must balance global progress with local, small-space computation.The paper presents these as fundamental roadblocks.Source: §1 · p. 4
2 The Multiplicative Weights Update Meta-Method
The multiplicative-weights framework uses a guessed optimum and an oracle to find dual witnesses that improve feasibility. Averaging witnesses and checking a primal solution provide ways to obtain a feasible dual and verify the guess.
2 The Multiplicative Weights Update Meta-Method
- For a guessed optimum α, the oracle seeks a dual witness y with c^T y = α and expected dual-constraint violation at most δ.The primal variables are interpreted as probabilities when measuring expected violation.Source: §2 · pp. 4–5
- If the oracle fails, this is an approximate certificate that the dual LP with objective at least α is infeasible.A feasible primal solution below α is one possible certificate.Source: §2 · p. 4
- Multiplicative updates use constraint violations to guide the weights, and the average of the resulting dual witnesses approximately satisfies all dual constraints.In the problems considered, scaling that average can ensure dual feasibility and yield an approximate dual solution.Source: §2 · p. 5
- A primal feasible solution of value at most (1 + O(δ))α verifies the guess, so the scheme focuses on the largest α for which the oracle has not failed.The primal value upper-bounds any feasible dual value.Source: §2 · p. 5
- Using different initial constraint weights and Υ_i values yields a corollary that removes the ln(n) dependency from Theorem 1.The section states that this refinement is used in Section 5.Source: §2 · p. 7
3 Warming Up: O( 1 ε3 log n)-pass Algorithms
The section develops multiplicative-weights LP algorithms for bipartite cardinality and weighted matching, then abstracts the oracle design and extends it to handle edge weights. Its results include (1−ε)-approximation algorithms and weighted-oracle guarantees.
3 Warming Up: O( 1 ε3 log n)-pass Algorithms
- The warm-up uses multiplicative weights and primal LP formulations to obtain (1−ε)-approximation algorithms for bipartite cardinality and weighted matching in O(1/ε^3 log n) passes.Source: §3 · p. 7
3.1 The Simple Case of MCM
- The cardinality-matching algorithm gives a (1−ε) approximation for bipartite graphs and a 2/3(1−ε) result for general graphs.Source: §3.1 · p. 8
3.2 Abstracting the Oracle
- The oracle balances admissibility and verification by matching among primal-violating edges, so every violated edge has a selected adjacent edge.Source: §3.2 · p. 9
3.3 The Not So Simple Case of MWM
- The weighted oracle retains at least one-fifth of candidate-edge weight in a matching and, with few violations, certifies primal value at most (1+5δ)α.Source: §3.3 · p. 11
- The weighted bipartite matching algorithm achieves a (1−ε) approximation using O(1/ε log n) space.Source: §3.3 · p. 12
4 Reducing the Space Requirement and the Number of Passes
This section examines ways to reduce space and passes in the approximation approach, including storing only computed y values and, for weighted matching, reusing admissible updates across guesses of α and a dual witness across iterations. It also describes the approach’s pass and iteration costs.
4.1 Reducing the Space Requirement
- Reusing one admissible update sequence across decreasing α-guesses avoids separate oracle copies, yielding O(n(T+log n)) space and T+O(1/ε^3 log n) passes.A sequence admissible for a larger α remains admissible for a smaller guess.Source: §4.1 · pp. 12–13
4.2 Reducing the number of passes
- Reusing an admissible dual witness for up to 1/δ iterations enables a (1−ε) approximation in T=O(1/ε^3 log n) iterations, with T+1 passes.The witness remains admissible throughout those iterations, so the algorithm need not recompute it at each step.Source: §4.2 · pp. 15–16
- With δ=ε/30, the approach achieves a (1−ε)-approximation; each y computation takes a pass, and inadmissibility can add O(1/ε) iterations.An iteration may need to be repeated when y is not admissible, as in Theorem 11.Source: §4.2 · p. 16
- The space requirement is O(n(T + log n)) because only the different computed y values need to be remembered.Source: §4.2 · p. 16
5 Removing the Dependency on n
This section removes dependence on the number of vertices from pass counts for maximum cardinality and weighted matching using reduced subgraphs and iteration bounds, and gives approximation guarantees for maximum weighted matching, including a charge-based procedure for the not-so-simple MWM case.
5 Removing the Dependency on n
- For both matching variants, the section adapts Algorithm 6 to an input subgraph and bounds its iterations; it also changes the initial weights and uses Corollary 2.The stated goal is to make the number of passes independent of the number of nodes.Source: §5 · p. 17
5.1 The Simple Case of MCM
- Every two rounds, the induced-subgraph matching deficit contracts to at most 2/3 of its previous value, and this lemma does not require bipartiteness.The deficit is the difference between OPT and the maximum matching size in the induced subgraph.Source: §5.1 · p. 17
- Algorithm 7 gives a (1−ε) approximation for bipartite maximum cardinality matching in O(1/ε) passes and O(n′(T + log n′)) space.The stated space bound uses n′; the supplied passage does not fully specify its definition.Source: §5.1 · p. 18
5.2 The Not So Simple Case of MWM
- With ν=ε′/8 and ε=ε′/2, the weighted approach yields a (1−ε′) approximation for maximum weighted matching in O(1/ν) passes.The analysis combines a (1−3ν) factor for the discretized instance with the loss from discretization.Source: §5.2 · p. 19
- For discretized edges, Algorithm 8 computes vertex weights as proxies for expressing the subgraph implicitly; in this discretized setting, G′ contains a matching with weight at least (1 −3ν)w(M′).Source: §5.2 · pp. 19–20
- The procedure updates M and F through neighborhood cases, maintains each F edge at least as heavy as the heaviest edge in M, and accounts for changes using red, green, and blue charges.Source: §5.2 · pp. 20–21
- A (1−ε)-approximation is obtained for bipartite maximum weighted matching, yielding a 2/3(1−ε)-approximation for general graphs via integrality-gap results.Source: §5.2 · p. 22
6 Extensions: the b-Matching Problem and the Maximum Matching Problem in General Graphs
Section 6 extends the paper’s algorithms to capacitated and uncapacitated bipartite b-matching and maximum weighted matching in general graphs. The extensions use different space–pass tradeoffs, with the capacitated case returning a fractional solution.
6.1 The Maximum (Capacitated) bipartite b-Matching Problem
- For capacitated bipartite b-matching, the algorithms give a (1−ε) approximation using O(BT) space and O(ε^-3 log n) passes.The returned solution is fractional, and space depends on edge and vertex capacities.Source: §6.1 · p. 24
6.2 The Maximum Uncapacitated b-Matching Problem
- Uncapacitated b-matching has two algorithmic tradeoffs: constant passes with space depending on B, or near-linear space with a pass count depending on log n.For weighted bipartite graphs, the near-linear-space algorithm gives a (1−ε) approximation in O(ε^-3 log n) passes and O(nT) space.Source: §6.2 · pp. 24–25
6.3 The Maximum Weight Matching Problem for General Graphs
- For general graphs, ignoring odd-set constraints for |U| > 1/δ leaves O(nδ^-1) constraints; the LP has a constraint for each odd vertex subset.Source: §6.3 · pp. 25–26
- For maximum weighted matching in general graphs, the algorithm computes a (1 − ε) approximation and uses O(nT) space.Source: §6.3 · p. 26