An accelerated continuous greedy algorithm for maximizing strong submodular functions

Abstract

An accelerated continuous greedy algorithm is proposed for maximization of a special class of non-decreasing submodular functions f:2X→R+ subject to a matroid constraint with a (Formula Presented.)(1-e-c-ε) approximation for any ε > 0, where c is the curvature with respect to the optimum. Functions in the special class of submodular functions satisfy the criterion ∀A,B⊆X,∀j∈X\(A∪B), ▵fj(A,B)=Δf(A∪{j})+f(B∪{j})-f((A∩B)∪{j})-f(A∪B∪{j})-[f(A)+f(B)-f(A∩B)-f(A∪B)]≤0. As an alternative to the standard continuous greedy algorithm, the proposed algorithm can substantially reduce the computational expense by removing redundant computational steps and, therefore, is able to efficiently handle the maxi..