An accelerated continuous greedy algorithm for maximizing strong submodular functions (Q887854)

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.