TY - JOUR
T1 - An accelerated continuous greedy algorithm for maximizing strong submodular functions
AU - Wang, Zengfu
AU - Moran, Bill
AU - Wang, Xuezhi
AU - Pan, Quan
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2015/11/1
Y1 - 2015/11/1
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Matroid
KW - Monotone submodular set function
UR - http://www.scopus.com/inward/record.url?scp=84944277736&partnerID=8YFLogxK
U2 - 10.1007/s10878-013-9685-x
DO - 10.1007/s10878-013-9685-x
M3 - 文章
AN - SCOPUS:84944277736
SN - 1382-6905
VL - 30
SP - 1107
EP - 1124
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 4
ER -