A tight analysis of the Submodular-Supermodular Procedure

作者：Byrnes Kevin M^*

来源：Discrete Applied Mathematics, 2015, 186: 275-282.

DOI：10.1016/j.dam.2015.01.026

• Submodularity
• Submodular-Supermodular Procedure
• Discrete optimization

Narasimhan and Bilmes introduced the Submodular-Supermodular Procedure (SSP) for finding a local minimizer of the function h = f - g where f and g are both submodular functions. In their original analysis the authors left the worst case complexity of SSP as an open question. We provide a tight analysis of SSP by demonstrating a family of examples where SSP can require 2(n-2) - 1 iterations before converging (although it reaches a global optimum). We also consider the related Supermodular-Submodular Procedure of lyer and Bilmes and demonstrate an example that requires >= left perpendicular16 * 3((n-8)/3) -3right perpendicular iterations to converge, and converges to a local, not global, optimum.

• 出版日期2015-5-11