The one-way communication complexity of submodular maximization with applications to streaming and robustness

DOI10.1145/3357713.3384286OpenAlexW3035181444MaRDI QIDQ5145019

Moran Feldman, Rico Zenklusen, Ola Svensson, Ashkan Norouzi-Fard

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

robustnessapproximation algorithmscommunication complexitystreamingsubmodular maximization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (8)

A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Streaming submodular maximization with the chance constraint ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ 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

This page was built for publication: The one-way communication complexity of submodular maximization with applications to streaming and robustness