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

submodular functionmultiplicative weight updates

Mathematics Subject Classification ID

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

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

(17)

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

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)