A Note on Submodular Function Minimization with Covering Type Linear Constraints

作者：Kamiyama Naoyuki^*

来源：Algorithmica, 2018, 80(10): 2957-2971.

DOI：10.1007/s00453-017-0363-8

• Submodular function minimization
• Primal-dual approximation algorithm

In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by the number of non-zero coefficients in the ith constraints. Furthermore, we assume that . For this problem, Koufogiannakis and Young proposed a polynomial-time -approximation algorithm. In this paper, we propose a new polynomial-time primal-dual approximation algorithm based on the approximation algorithm of Takazawa and Mizuno for the covering integer program with -variables and the approximation algorithm of Iwata and Nagano for the submodular function minimization problem with set covering constraints. The approximation ratio of our algorithm is , where is the maximum size of a connected component of the input submodular function.

• 出版日期2018-10