Submodular maximization meets streaming: matchings, matroids, and more

DOI10.1007/s10107-015-0900-7zbMath1342.90212arXiv1309.2038OpenAlexW1989151913MaRDI QIDQ896286

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)

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

zbMATH Keywords

submodular functionmaximum matchingmultiple matroid

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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