An accelerated continuous greedy algorithm for maximizing strong submodular functions

Zengfu Wang, Bill Moran, Xuezhi Wang, Quan Pan

科研成果: 期刊稿件文章同行评审

4 引用 (Scopus)

摘要

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 maximization problems for this special class of submodular functions. Examples of such functions are presented.

源语言英语
页(从-至)1107-1124
页数18
期刊Journal of Combinatorial Optimization
30
4
DOI
出版状态已出版 - 1 11月 2015

指纹

探究 'An accelerated continuous greedy algorithm for maximizing strong submodular functions' 的科研主题。它们共同构成独一无二的指纹。

引用此