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

Zhenning Zhang, Donglei Du, Yanjun Jiang () and Chenchen Wu
Additional contact information
Zhenning Zhang: Beijing University of Technology
Donglei Du: University of New Brunswick
Yanjun Jiang: School of Mathematics and Statistics Science, Ludong University
Chenchen Wu: College of Science, Tianjin University of Technology

Journal of Global Optimization, 2021, vol. 80, issue 3, No 4, 595-616

Abstract: Abstract 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.

Keywords: DR-submodular function; Supermodular function; Cardinality constraint; Threshold greedy algorithm; Total curvature (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01014-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:80:y:2021:i:3:d:10.1007_s10898-021-01014-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01014-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().