Robust Monotone Submodular Function Maximization

DOI10.1007/978-3-319-33461-5_26zbMath1419.90107OpenAlexW2962907715MaRDI QIDQ3186512

James B. Orlin, Andreas S. Schulz, Rajan Udwani

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/129591

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Nonlinear programming (90C30)

Related Items

Streaming algorithms for robust submodular maximization, A Branch-and-Cut Algorithm for Submodular Interdiction Games, Structured Robust Submodular Maximization: Offline and Online Algorithms, Randomized strategies for robust combinatorial optimization with approximate separation, Running time analysis of the (1+1)-EA for robust linear optimization, Robust budget allocation via continuous submodular functions, Approximating Robust Parameterized Submodular Function Maximization in Large-Scales

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust discrete optimization and network flows
• A note on maximizing a submodular set function subject to a knapsack constraint
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Symmetry and Approximability of Submodular Maximization Problems
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
• Maximizing Non-monotone Submodular Functions
• Theory and Applications of Robust Optimization
• A threshold of ln n for approximating set cover
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• The Price of Robustness
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• From query complexity to computational complexity
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• A Unified Continuous Greedy Algorithm for Submodular Maximization