Maximizing DR-submodular plus supermodular functions on the integer lattice subject to a cardinality constraint

作     者：Zhang, Zhenning Du, Donglei Jiang, Yanjun Wu, Chenchen 

作者机构：Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada Ludong Univ Sch Math & Stat Sci 186 Hongqi Middle Rd Yantai 264025 Shandong Peoples R China Tianjin Univ Technol Coll Sci 391 Binshui West St Tianjin Peoples R China 

出 版 物：《JOURNAL OF GLOBAL OPTIMIZATION》 (全局最优化杂志)

年 卷 期：2021年第80卷第3期

页      面：595-616页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Natural Science Foundation of China [12001025, 11871081, 11771386, 11728104, 11801251, 11971349] Science and Technology Program of Beijing Education Commission [KM201810005006] Natural Sciences and Engineering Research Council of Canada Academy of Finland (AKA) Funding Source: Academy of Finland (AKA) 

主　　题：DR-submodular function Supermodular function Cardinality constraint Threshold greedy algorithm Total curvature 

摘      要：Arising from practical problems such as in sensor placement and influence maximization in social network, submodular and non-submodular maximization on the integer lattice has attracted much attention recently. In this work, we consider the problem of maximizing the sum of a monotone non-negative diminishing return submodular (DR-submodular) function and a supermodular function on the integer lattice subject to a cardinality constraint. By exploiting the special combinatorial structures in the problem, we introduce a decreasing threshold greedy algorithm with a binary search as its subroutine to solve the problem. To avoid introducing the diminishing return ratio and submodularity ratio of the objective function, we generalize the total curvatures of submodular functions and supermodular functions to the integer lattice version. We show that our algorithm has a constant approximation ratio parameterized by the new introduced total curvatures on integer lattice with a polynomial query complexity.