Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

Zhenning Zhang (), Longkun Guo, Yishui Wang (), Dachuan Xu () and Dongmei Zhang ()
Additional contact information
Zhenning Zhang: Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China
Longkun Guo: Shandong Key Laboratory of Computer Networks, School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, Shandong 250353, P. R. China
Yishui Wang: School of Mathematics and Physics, University of Science and Technology Beijing, Beijing 100083, P. R. China
Dachuan Xu: Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China
Dongmei Zhang: School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-14

Abstract: Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio 1 2 − 𝜖. The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to O(k 𝜖 ) and the query complexity to O(klog2k 𝜖 ).

Keywords: Diminishing return submodular; submodular maximization; integer lattice; cardinality; streaming algorithm (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921400042
Access to full text is restricted to subscribers

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:wsi:apjorx:v:38:y:2021:i:05:n:s0217595921400042

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921400042

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().