Journal article

An accelerated continuous greedy algorithm for maximizing strong submodular functions

Zengfu Wang, Bill Moran, Xuezhi Wang, Quan Pan

JOURNAL OF COMBINATORIAL OPTIMIZATION | SPRINGER | Published : 2015

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..

View full abstract

Grants

Awarded by NSFC


Awarded by AFOSR


Funding Acknowledgements

The first author is thankful for having communicated with Dr Jan Vondrak to discuss the continuous greedy algorithm. The authors also wish to acknowledge the anonymous reviwers/referees for their constructive comments and suggestions for this work. This work was supported in part by the NSFC(No. 61135001) and the AFOSR Grant (FA2386-13-1-4080).