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

DOI10.1145/3357713.3384286MaRDI QIDQ5145019zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Streaming algorithms for robust submodular maximization
• Communication complexity of combinatorial auctions with submodular valuations
• Robust lower bounds for communication and stream computation
• Streaming algorithms for submodular function maximization
• A survey on streaming algorithms for maximizing submodular functions
• Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• scientific article; zbMATH DE number 7053293
• Streaming and communication complexity of clique approximation

Cited in

(9)

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

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