Minimum non-submodular cover problem with applications

Highlights：

• We analyze the performance of the greedy algorithm for Non-submodular Cover problem and give two theoretical guarantees, with either integer-valued or fraction-valued non-submodular function.

• We analyze the values of parameters of DR gap and DR ratio for DS function and BP function. When it comes to DS function f=g−h, DR gap a=khδh, where kh is the total curvature for submodular function h and δh=max{h({i}):i∈V}. In the case of BP function f=g+h, DR ratio ξ=1−kh, where kh is the supermodular curvature for supermodular function h.

• We present several real-world applications which can be reduced to Minimum Non-submodular Cover problem, including the determinantal function in video summarization, influence spread in online social networks and so on.

摘要

•We analyze the performance of the greedy algorithm for Non-submodular Cover problem and give two theoretical guarantees, with either integer-valued or fraction-valued non-submodular function.•We analyze the values of parameters of DR gap and DR ratio for DS function and BP function. When it comes to DS function f=g−h, DR gap a=khδh, where kh is the total curvature for submodular function h and δh=max{h({i}):i∈V}. In the case of BP function f=g+h, DR ratio ξ=1−kh, where kh is the supermodular curvature for supermodular function h.•We present several real-world applications which can be reduced to Minimum Non-submodular Cover problem, including the determinantal function in video summarization, influence spread in online social networks and so on.

论文评审过程：Received 13 September 2020, Revised 4 June 2021, Accepted 6 June 2021, Available online 24 June 2021, Version of Record 24 June 2021.