TY - JOUR
T1 - A Note on Submodular Function Minimization with Covering Type Linear Constraints
AU - Kamiyama, Naoyuki
N1 - Funding Information:
Acknowledgements The author would like to thank Naonori Kakimura and the anonymous referees for helpful comments. This research was supported by JST PRESTO Grant Number JPMJPR14E1, Japan.
Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - 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 Δi the number of non-zero coefficients in the ith constraints. Furthermore, we assume that Δ1≥ Δ2≥ ⋯ ≥ Δm. For this problem, Koufogiannakis and Young proposed a polynomial-time Δ1-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 { 0 , 1 } -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 max { Δ2, min { Δ1, 1 + Π} } , where Π is the maximum size of a connected component of the input submodular function.
AB - 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 Δi the number of non-zero coefficients in the ith constraints. Furthermore, we assume that Δ1≥ Δ2≥ ⋯ ≥ Δm. For this problem, Koufogiannakis and Young proposed a polynomial-time Δ1-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 { 0 , 1 } -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 max { Δ2, min { Δ1, 1 + Π} } , where Π is the maximum size of a connected component of the input submodular function.
UR - http://www.scopus.com/inward/record.url?scp=85028537386&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028537386&partnerID=8YFLogxK
U2 - 10.1007/s00453-017-0363-8
DO - 10.1007/s00453-017-0363-8
M3 - Article
AN - SCOPUS:85028537386
SN - 0178-4617
VL - 80
SP - 2957
EP - 2971
JO - Algorithmica
JF - Algorithmica
IS - 10
ER -