Submodular maximization meets streaming: matchings, matroids, and more

DOI10.1007/978-3-319-07557-0_18zbMATH Open1342.90212arXiv1309.2038OpenAlexW1989151913MaRDI QIDQ896286FDOQ896286

Amit Chakrabarti, Sagar Kale

Publication date: 9 December 2015

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: 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(nlogn)$ working memory---that achieve approximation ratios of $7.75$ in a single pass and $(3+epsilon)$ in $O(epsilo{n}^{-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.

Full work available at URL: https://arxiv.org/abs/1309.2038

zbMATH Keywords

submodular functionmaximum matchingmultiple matroid

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Efficient algorithms for finding maximum matching in graphs
• On graph problems in a semi-streaming model
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Title not available (Why is that?)
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• Weighted Matching in the Semi-Streaming Model
• Proceedings of the forty-first annual ACM symposium on Theory of computing

Cited In (40)

• Approximating Robust Parameterized Submodular Function Maximization in Large-Scales
• Streaming algorithms for robust submodular maximization
• Submodular maximization meets streaming: matchings, matroids, and more
• Matroid-constrained vertex cover
• Streaming Algorithms for Submodular Function Maximization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
• The Power of Subsampling in Submodular Maximization
• Better streaming algorithms for the maximum coverage problem
• Small Space Stream Summary for Matroid Center
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Title not available (Why is that?)
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Semi-streaming algorithms for submodular function maximization under \(b\)-matching, matroid, and matchoid constraints
• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Online Submodular Maximization with Preemption
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
• Title not available (Why is that?)
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Non-submodular maximization on massive data streams
• Sequence submodular maximization meets streaming
• Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
• Submodular maximization over data streams with differential privacy noise
• On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Almost-smooth histograms and sliding-window graph algorithms
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Online budgeted maximum coverage

   Recommendations

• Submodular maximization meets streaming: matchings, matroids, and more 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Streaming Algorithms for Submodular Function Maximization 👍 👎
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints 👍 👎
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint 👍 👎
• Semi-streaming algorithms for submodular matroid intersection 👍 👎
• Semi-streaming algorithms for submodular matroid intersection 👍 👎
• Streaming submodular maximization under \(d\)-knapsack constraints 👍 👎
• Streaming algorithms for robust submodular maximization 👍 👎

This page was built for publication: Submodular maximization meets streaming: matchings, matroids, and more

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896286)