On multiplicative weight updates for concave and submodular function maximization

DOI10.1145/2688073.2688086MaRDI QIDQ2989031zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, T. S. Jayram, Jan Vondrák

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2688073.2688086

zbMATH Keywords

multiplicative weight updatessubmodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Fast algorithms for maximizing submodular functions
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• scientific article; zbMATH DE number 7255156
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular function maximization in parallel via the multilinear relaxation

Cited in

(20)

• Stochastic block-coordinate gradient projection algorithms for submodular maximization
• Private non-monotone submodular maximization
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Measured continuous greedy with differential privacy
• Algorithms for covering multiple submodular constraints and applications
• Streaming algorithms for submodular function maximization
• Stochastic conditional gradient methods: from convex minimization to submodular maximization
• Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
• Submodular Optimization with Contention Resolution Extensions.
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Stochastic Variance Reduction for DR-Submodular Maximization
• Online non-monotone diminishing return submodular maximization in the bandit setting
• Subquadratic submodular maximization with a general matroid constraint
• Covering a few submodular constraints and applications
• Online happiness maximization queries

This page was built for publication: On multiplicative weight updates for concave and submodular function maximization

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