An accelerated continuous greedy algorithm for maximizing strong submodular functions
A submodular function \(f:2^{X} \rightarrow \mathbb{R}_{+}\) is \textit{strong submodular}, if \( \forall A, B \subseteq X, \forall j \in X \setminus (A \cup B)\), \(f(A \cup \{j\})+f(B \cup \{j\})-f((A \cap B) \cup \{j\})-f(A \cup B\cup \{j\}) \leq f(A)+f(B)-f(A \cap B)-f(A \cup B)\). For a submodular and non-decreasing such function \(f\) and a matroid \(M=(X,\mathcal{I})\), the authors consider the optimization problem \(\max \{f(S): S \in \mathcal{I}\}\). Based on the \textit{(standard) continuous greedy algorithm (SCGA)} introduced by \textit{J. Vondrák} [RIMS Kôkyûroku Bessatsu B23, 253--266 (2010; Zbl 1219.68109)], an \textit{accelerated continuous greedy algorithm (ACGA)} is presented, which achieves the same degree of approximation as that of \(SCGA\), namely \(1/c(1-e^{-c}-\epsilon)\) for any \(\epsilon >0\), and where \(c\) is the curvature with respect to the optimum, but which substantially reduces the computational expense by removing redundant computational steps. Comparative computational results are given for weighted set coverage and strong submodular welfare problems.
- scientific article; zbMATH DE number 5888315
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Fast algorithms for maximizing submodular functions
- Optimal approximation for the submodular welfare problem in the value oracle model
- Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- A note on maximizing a submodular set function subject to a knapsack constraint
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Combinatorial auctions with decreasing marginal utilities
- Comments on bases in dependence structures
- scientific article; zbMATH DE number 5888315 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- Inapproximability results for combinatorial auctions with submodular utility functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- Maximizing submodular set functions subject to multiple linear constraints
- Optimal approximation for the submodular welfare problem in the value oracle model
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
- The power of local search: maximum coverage over a matroid
This page was built for publication: An accelerated continuous greedy algorithm for maximizing strong submodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q887854)
