Robust monotone submodular function maximization

DOI10.1007/S10107-018-1320-2MaRDI QIDQ1801019zbMATH OpenOpenAlexWikidataFDO

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

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, https://hdl.handle.net/1721.1/129591

zbMATH Keywords

approximation algorithmsubmodular function maximizationrobust maximization

Mathematics Subject Classification ID

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

Abstract: We consider a robust formulation, introduced by Krause et al. (2008), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to $au$ elements from the chosen set. For the fundamental case of $au=1$, we give a deterministic $(1-1/e)-1/Theta(m)$ approximation algorithm, where $m$ is an input parameter and number of queries scale as $O(n^{m+1})$. In the process, we develop a deterministic $(1-1/e)-1/Theta(m)$ approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (2010), we show a randomized $(1-1/e)-epsilon$ approximation for constant $au$ and $epsilonleqfrac1ildeOmega(au)$, making $O(n^{1/epsilo{n}^3})$ queries. Further, for $aullsqrtk$, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System.

Recommendations

• Robust monotone submodular function maximization
• Fast algorithms for maximizing submodular functions
• Approximating robust parameterized submodular function maximization in large-scales
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Monotone submodular maximization over a matroid via non-oblivious local search

Cites work

• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• 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
• Maximizing Non-monotone Submodular Functions
• Maximizing a monotone submodular function subject to a matroid constraint
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Optimal approximation for the submodular welfare problem in the value oracle model
• Robust discrete optimization and network flows
• Robust optimization
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular maximization by simulated annealing
• Symmetry and approximability of submodular maximization problems
• The Price of Robustness
• Theory and applications of robust optimization

Cited in

(23)

• Submodular maximization with uncertain knapsack capacity
• Robust submodular minimization with applications to cooperative modeling
• Data-driven robust resource allocation with monotonic cost functions
• Unified Greedy Approximability beyond Submodular Maximization
• Robust maximum capture facility location under random utility maximization models
• Robust monotone submodular function maximization
• Algorithms for maximizing monotone submodular function minus modular function under noise
• Robust budget allocation via continuous submodular functions
• Efficient algorithms for \(k\)-submodular function maximization with \(p\)-system and \(d\)-knapsack constraint
• Approximating robust parameterized submodular function maximization in large-scales
• Greedy algorithm for maximization of semi-monotone non-submodular functions with applications
• Unified greedy approximability beyond submodular maximization
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• Adaptive robust submodular optimization and beyond
• Network inspection for detecting strategic attacks
• Robust Maximization of Correlated Submodular Functions Under Cardinality and Matroid Constraints
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Submodular maximization with uncertain knapsack capacity
• Stability and recovery for independence systems
• Randomized greedy methods for weak submodular sensor selection with robustness considerations
• Fractionally subadditive maximization under an incremental knapsack constraint
• The submodularity of two-stage stochastic maximum-weight independent set problems
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)

This page was built for publication: Robust monotone submodular function maximization

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