Robust monotone submodular function maximization

DOI10.1007/s10107-018-1320-2zbMath1401.90261arXiv1507.06616OpenAlexW3100003759WikidataQ129231706 ScholiaQ129231706MaRDI QIDQ1801019

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

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsubmodular function maximizationrobust maximization

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Network Inspection for Detecting Strategic Attacks, Robust maximum capture facility location under random utility maximization models, 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, Adaptive robust submodular optimization and beyond, Fractionally subadditive maximization under an incremental knapsack constraint, The submodularity of two-stage stochastic maximum-weight independent set problems, Data-Driven Robust Resource Allocation with Monotonic Cost Functions

Cites Work

• Unnamed Item
• 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
• Deterministic Algorithms for Submodular Maximization Problems
• Fast algorithms for maximizing submodular functions
• 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