Source-linked AI summary
Submodular Maximization Meets Streaming: Matchings, Matroids, and More
Amit Chakrabarti, Sagar Kale
TL;DR
The paper studies maximizing a monotone submodular function over matchings in arbitrary-order graph streams. It adapts a general MWM algorithmic framework to MSM and obtains semi-streaming guarantees of 7.75 in one pass and (3 + ε) in O(ε^-3) passes, while extending the framework to broader independence constraints.
Problem
The paper asks how to find maximum submodular-function matchings from arbitrary-order graph streams using semi-streaming space.
Method
The paper identifies a framework for adapting MWM streaming algorithms to MSM and analyzes adaptations of Zelke’s and McGregor’s algorithms.
Results
7.75 in one pass and (3 + ε) in O(ε^-3) passes are achieved using O(n) stored edges and O(n log n) working memory.
Takeaways & Limitations
The framework also yields streaming results for submodular maximization over hypermatchings and intersections of multiple matroids.
Takeaways & Limitations
No polynomial-time C-approximation exists for f-MSM relative to a value oracle when C < e/(e −1).
Abstract
from arXiv · showhide
We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM), which is in turn a generalization of maximum cardinality matching (MCM). We give two incomparable algorithms for this problem with space usage falling in the semi-streaming range---they store only $O(n)$ edges, using $O(n\log n)$ working memory---that achieve approximation ratios of $7.75$ in a single pass and $(3+ε)$ in $O(ε^{-3})$ passes respectively. The operations of these algorithms mimic those of Zelke's and McGregor's respective algorithms for MWM; the novelty lies in the analysis for the MSM setting. In fact we identify a general framework for MWM algorithms that allows this kind of adaptation to the broader setting of MSM. In the sequel, we give generalizations of these results where the maximization is over "independent sets" in a very general sense. This generalization captures hypermatchings in hypergraphs as well as independence in the intersection of multiple matroids.
1 Introduction
The paper introduces maximum submodular matching for arbitrary-order graph streams and develops semi-streaming algorithms, a reusable framework, and extensions to broader independence constraints.
- Problem setting: MSM maximizes a monotone submodular function over matchings in an arbitrary-order graph stream, extending maximum weight and cardinality matching.The problem is motivated by streaming graph data and applications such as word alignment.
- Problem setting: O(n log n) working memory supports both semi-streaming algorithms, each storing only O(n) edges.The streaming model requires sequential edge access and permits multiple passes.
- Results: 7.75 is achieved by the one-pass algorithm, which stores at most O(n) edges.This is the paper’s one-pass guarantee for f-MSM.
- Results: (3 + ε) is achieved in O(ε^-3) passes by a multi-pass algorithm that stores only a matching.The two approximation algorithms are incomparable.
- Technique: A general framework adapts MWM streaming algorithms to MSM, with novel analysis enabling the results from Zelke’s and McGregor’s algorithms.The framework assigns edge weights according to improvement to the current matching and supports weights recalculated across passes.
- Extensions: The framework extends beyond matchings to hypermatchings and maximization over intersections of p matroids.These extensions define MSIS and MWIS variants with near-linear-space streaming guarantees.
- Curvature: Approximation ratios improve toward the corresponding MWM and MWIS ratios as curv(f) approaches zero, although the general ratios are otherwise worse.The curvature satisfies curv(f) = 0 exactly when f is modular.
- Context: The streaming algorithms trade slightly weaker approximation guarantees for faster computation and compatibility with graph streams.The paper contrasts them with offline greedy and local-search approaches that are unsuitable for graph streams.
2 Preliminaries
The paper formulates MSM as submodular maximization over streamed graph matchings and develops a general framework for extending compliant MWIS algorithms to f-MSIS. The model uses a value oracle for f and supports semi-streaming algorithms that retain only a small portion of the edge set.
- Problem formulation: The value oracle supplies f(S) for subsets S of streamed edges, while the algorithm may remember only a tiny portion of E.Oracle queries outside E are prohibited to prevent indirect access to the full edge set.
- Problem formulation: MSM maximizes a non-negative monotone proper submodular function over independent sets, with matchings as its graph-specific case.The framework also encompasses broader f-MSIS instances where independence can be tested efficiently.
- Framework: The generic f-MSIS algorithm starts from an independent set, processes the stream in a pretend order, and maintains a current solution, shadow elements, and element weights.It uses augmenting pairs and a parameter γ to improve the independent set during a pass.
- Framework: An MWIS algorithm is compliant when each pass invokes the generic improvement procedure from the previous solution, and an f-extension reuses its augmentation logic with submodularly assigned weights.This yields a modular-to-submodular transfer framework.
- Applications: The framework adapts Zelke’s one-pass MWM algorithm and McGregor’s multi-pass algorithm to obtain the paper’s MSM results.The paper organizes these applications as the one-pass and multi-pass f-MSM constructions.
3 A One-Pass Solution via Compliant Algorithms
The one-pass analysis bounds the submodular optimum through the maintained solution and removed elements, allowing compliant MWIS guarantees to transfer to f-MSIS. Applied to Zelke’s algorithm, this gives a 7.75-approximation for f-MSM.
- Analysis: The f-extension assigns each processed element a marginal value relative to the current solution and shadow set.This preserves the generic framework’s weight-based analysis while using submodular marginal gains.
- Analysis: The total weight of killed elements satisfies w(K) ⩽ w(I)/γ, while the maintained solution satisfies w(I) ⩽ f(I).These inequalities control the contribution of removed elements in the approximation proof.
- Analysis: The analysis establishes f(I*) ⩽ (1/γ + 1)f(I) + w(I*), linking the submodular optimum to the output and its induced weights.The bound follows by separating elements in the final solution, killed elements, and the optimum.
- Transfer lemma: 119? The compliant MWIS guarantee converts the preceding inequality into the generic ratio Cγ + 1 + 1/γ for f-MSIS.This is the modular-to-submodular transfer used by the framework.
- Application to f-MSM: 7.75 is the resulting one-pass approximation ratio for f-MSM using Zelke’s algorithm, attained at γ = 1.Zelke’s compliant ratio gives 2(1 + γ)^2/γ − γ/(1 + γ)^2, minimized at 7.75.
4 A Multi-Pass MSM Algorithm
The multi-pass algorithm extends McGregor’s matching procedure by assigning submodular marginal weights and repeatedly improving the matching. It achieves a (3 + ε)-approximation in O(ε^-3) passes while storing only O(n) edges.
- Algorithm: McGregor’s multi-pass MWM algorithm is adapted by using submodular marginal weights and repeatedly invoking matching improvement.The extension uses γ = 1 for the first pass and γ = ε/3 thereafter.
- Analysis: Each newly added edge can kill at most two matching edges, and the analysis organizes these events into disjoint rooted killing trees.Edges already in the previous matching are initially restored in the pretend order and are not reconsidered during that pass.
- First pass: The first pass produces an 8-approximate f-MSM solution.The first-pass bound is minimized at γ = 1.
- Space and proof: The multi-pass algorithm stores only a matching, hence O(n) edges, and its analysis repairs a gap caused by a subtlety in McGregor’s argument.The pretend stream order fixes the issue identified in the paper.
- Analysis: The stopping criterion and weight-transfer lemmas bound the remaining improvement across passes, despite weights changing between passes.The changing weight functions make the pass analysis more involved than in the corresponding MWM argument.
- Guarantee: (3 + ε) is the final approximation ratio, achieved after O(ε^-3) passes.The pass bound follows from τ ⩽ 2 + log_(1+κ) 8 = O(κ^-1) = O(ε^-3).
5 Generalization to Matchings in Hypergraphs
The paper extends streaming matching algorithms from graphs to p-hypergraphs, using generalized charging arguments to obtain semi-streaming approximation guarantees for MWM and MSM.
- 5 Generalization to Matchings in Hypergraphs: Approximation ratios for p-hypergraph MSM are 4p in one pass and p + 1 + ε with O(ε^-3 log p) passes.The algorithms use O(n log n) space, where n := |V| and m := |E| ≤ np.
- 5 Generalization to Matchings in Hypergraphs: Approximation ratios for p-hypergraph MWM are 2(p + p(p −1)) −1 in one pass and p + ε with O(ε^-3 log p) passes.
- 5 Generalization to Matchings in Hypergraphs: The hypergraph analysis generalizes the charging scheme by redistributing optimum-edge weights among edges in the algorithm’s matching and auxiliary set.The resulting bounds depend on whether an edge is in the final matching or in the auxiliary set.
6 Maximization Over (Multiple) Matroids
The paper extends streaming submodular maximization to intersections of multiple matroids, providing space-efficient algorithms and approximation guarantees for modular and submodular objectives.
- 6 Maximization Over (Multiple) Matroids: The multiple-matroid problem maximizes a nonnegative monotone proper submodular function over sets independent in all p matroids.
- 6 Maximization Over (Multiple) Matroids: The algorithms use O(n(log m)^O(1)) memory, where n is the largest feasible-set size and m is the ground-set cardinality.
- 6 Maximization Over (Multiple) Matroids: For partition matroids, the approximation ratios are p + ε for modular objectives and p + 1 + ε for submodular objectives.These guarantees use O(ε^-3) passes through parameter choices for γ and κ.
- 6 Maximization Over (Multiple) Matroids: The approach reuses compliant one-pass algorithms and charging schemes to extend streaming guarantees from modular to submodular objectives.
A Details of the Charging Schemes
The appendix details a charging-and-redistribution proof for graph matchings, bounding how much optimum matching weight can be assigned to selected and auxiliary edges.
- A Details of the Charging Schemes: The proof charges the weight of an arbitrary matching M* to edges in M ∪ K, with per-edge bounds determined by membership in K or M.Each edge in K receives at most (1 + γ)w(e), while each edge in M receives at most 2(1 + γ)w(e).
- A Details of the Charging Schemes: Charges are assigned according to whether an optimum edge is born and later killed, survives, or is blocked by one or two selected edges.
- A Details of the Charging Schemes: At most (1 + γ)w(xy) charge is associated with each endpoint of an edge xy in M ∪ K.
- A Details of the Charging Schemes: When an edge is killed, charge associated with the shared vertex is transferred to the killing edge, whose weight is at least as large.
- A Details of the Charging Schemes: After redistribution, each auxiliary edge has charge associated with at most one vertex and each matching edge with at most two vertices.
A.1 Charging Scheme for Hypergraphs
The hypergraph charging scheme distributes optimum weight across intersecting edges and preserves bounded charge under redistribution, yielding the stated hypergraph approximation analysis.
- A.1 Charging Scheme for Hypergraphs: For hypergraphs, each auxiliary edge receives at most (p −1)(1 + γ)w(e) charge and each final matching edge at most p(1 + γ)w(e).
- A.1 Charging Scheme for Hypergraphs: An optimum edge killed later transfers its charge to the murdering edge through their shared vertices, while blocked edges distribute charge among at most p blockers.
- A.1 Charging Scheme for Hypergraphs: Redistribution transfers only charge associated with vertices in the intersection of the killed and killing edges.The resulting bounds give Equation (8).
B Ashwinkumar’s Algorithm and a New Charging Scheme
The section presents a one-pass algorithm for maximizing weight over independent sets constrained by multiple matroids, using circuit-based replacements during the stream.
- Matroid constraints: Partition matroids impose per-partition cardinality constraints, with independence defined by |I ∩ Ej| ≤ kj for every part.The construction also introduces circuits and saturation to characterize when adding an element violates a matroid constraint.
- Algorithm: For each arriving element e, the algorithm identifies one smallest-weight circuit element for each of the p matroids.These elements are denoted e1,...,ep and are computed from the circuits Ci(I + e).
- Algorithm: Algorithm 3 processes stream elements sequentially while maintaining an independent set I, initially empty.For each arriving element, it examines the smallest-weight elements in the relevant circuits created by adding that element.
- Algorithm: An arriving element replaces the identified circuit elements only when w(e) ≥ (1 + γ)w({e1,...,ep}).The update removes the selected elements and inserts e, preserving the algorithm’s weight-improvement threshold.
B.1 A Simpler Charging Scheme For Partition Matroids
The section develops a charging argument for multiple matroids, organizing killed elements into killing trees and redistributing charges to bound the approximation ratio.
- Charging structure: Elements added and later removed form disjoint rooted killing trees whose roots are the elements in the final output I.Each killed element’s parent is the element that killed it, and K consists of strict descendants of final elements.
- Initial charging: Optimal elements charge maintained elements when adding them would create a circuit in one of the matroids, while taken optimal elements charge themselves across all p matroids.Charges are associated with the matroid responsible for the circuit-based obstruction.
- Initial charging: When an optimal element is rejected, every corresponding circuit element has weight greater than w(e)/(1 + γ), and saturation limits how many optimal elements can charge it for each matroid.The argument selects uncharged circuit elements using the saturation and cardinality constraints.
- Charge redistribution: After redistribution, each killed element carries at most (p − 1)(1 + γ)w(e′) charge, while each final element carries at most p(1 + γ)w(e′).The redistribution transfers charges associated with each matroid while preventing repeated charging for a matroid.
- Approximation results: The multi-pass extension achieves approximation ratios p + ε for modular objectives and p + 1 + ε for submodular objectives.These bounds use γ = ε/(p + 1), with different κ settings for the linear and submodular cases.
C Zelke’s Algorithm for MWM
Zelke’s algorithm maintains a matching and a bounded collection of shadow edges, evaluating local augmenting sets when new stream edges arrive.
- Shadow edges: For each matching edge uv, the algorithm stores at most two shadow edges, one associated with each endpoint.These shadow edges provide local alternatives around the maintained matching.
- Local neighborhood: When an edge y1y2 arrives, the algorithm forms a local set T containing at most seven nearby edges.The set includes the arriving edge, intersecting matching edges, and shadow edges associated with their endpoints.
- Augmentation rule: The algorithm chooses a matching augmenting set A ⊆ T maximizing w(A) − (1 + γ)w(M ↱ A).Here, M ↱ A denotes maintained matching edges sharing vertices with edges in A.
- Update rule: The matching is updated only when the maximizing difference is positive.Afterward, shadow edges associated with removed matching edges are reassigned to the vertices shared with the new matching edges.
- Space maintenance: Removing shadow edges associated with M ↱ A keeps the total number of stored shadow edges at most n.The update therefore preserves the semi-streaming storage bound for this maintained structure.