摘要

We consider an application of the minimum-norm-point algorithm to submodular function minimization. Although combinatorial polynomial algorithms for submodular function minimization (SFM) have recently been obtained, there still remain (open) problems of reducing the complexity of the SFM algorithms and of constructing a practically fast SFM algorithms. We show some possible approach to the problems by means of the minimum-norm-point algorithm. Computational results on submodular function minimization reveal that our algorithm outperforms existing polynomial algorithms for SFM.

  • 出版日期2011-1