Robust monotone submodular function maximization

DOI10.1007/S10107-018-1320-2zbMATH Open1401.90261arXiv1507.06616OpenAlexW3100003759WikidataQ129231706 ScholiaQ129231706MaRDI QIDQ1801019FDOQ1801019

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)

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.

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

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

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)

Cites Work

• A threshold of ln n for approximating set cover
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Theory and applications of robust optimization
• Robust optimization
• The Price of Robustness
• Robust discrete optimization and network flows
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Maximizing Non-monotone Submodular Functions
• A note on maximizing a submodular set function subject to a knapsack constraint
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular maximization by simulated annealing
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Symmetry and approximability of submodular maximization problems
• From query complexity to computational complexity
• Deterministic algorithms for submodular maximization problems
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Title not available (Why is that?)
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)

Cited In (22)

• 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
• Algorithms for maximizing monotone submodular function minus modular function under noise
• Robust monotone submodular function maximization
• Robust budget allocation via continuous submodular functions
• Efficient algorithms for \(k\)-submodular function maximization with \(p\)-system and \(d\)-knapsack constraint
• Greedy algorithm for maximization of semi-monotone non-submodular functions with applications
• Approximating robust parameterized submodular function maximization in large-scales
• Unified greedy approximability beyond submodular maximization
• 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
• Title not available (Why is that?)
• Submodular maximization with uncertain knapsack capacity

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)