Structured Robust Submodular Maximization: Offline and Online Algorithms

DOI10.1287/IJOC.2020.0998MaRDI QIDQ5084617zbMATH OpenOpenAlexFDO

Authors Mohit Singh, Sebastian Pokutta, Nika Haghtalab, Joseph (Seffi) Naor, Nima Anari, Alfredo Torrico

Publication date 28 June 2022

Published in INFORMS Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmmatroid constraintsonline learningrobust optimizationsubmodular optimization

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Robust monotone submodular function maximization
• Adaptive robust submodular optimization and beyond
• Robust monotone submodular function maximization
• Streaming algorithms for robust submodular maximization
• Online risk-averse submodular maximization

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• An analysis of the greedy algorithm for the submodular set covering problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Deterministic algorithms for submodular maximization problems
• Efficient algorithms for online decision problems
• Fast algorithms for maximizing submodular functions
• Finding Groups in Data
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Maximizing a monotone submodular function subject to a matroid constraint
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Non-monotone submodular maximization under matroid and knapsack constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Optimization models
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Robust monotone submodular function maximization
• Submodular maximization with cardinality constraints

Cited in

(11)

• Fractionally subadditive maximization under an incremental knapsack constraint
• Robust Maximization of Correlated Submodular Functions Under Cardinality and Matroid Constraints
• scientific article; zbMATH DE number 7525448 (Why is no real title available?)
• Unified Greedy Approximability beyond Submodular Maximization
• Unified greedy approximability beyond submodular maximization
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Online dynamic submodular optimization
• Two-sided capacitated submodular maximization in gig platforms
• Randomized greedy methods for weak submodular sensor selection with robustness considerations
• Practical proximal primal-dual algorithms for structured saddle point problems
• From global to query-dependent: summarization of large hierarchical DAGs

Describes a project that uses

Uses Software

• clusfind
• PASCAL VOC

This page was built for publication: Structured Robust Submodular Maximization: Offline and Online Algorithms

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