Efficient Streaming Algorithms for Maximizing Monotone DR-Submodular Function on the Integer Lattice

Bich-Ngan T. Nguyen, Phuong N. H. Pham (), Le Van-Vang and Václav Snášel
Additional contact information
Bich-Ngan T. Nguyen: Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh City 700000, Vietnam
Phuong N. H. Pham: Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh City 700000, Vietnam
Le Van-Vang: Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City 700000, Vietnam
Václav Snášel: Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 17.listopadu 15/2172, 708 33 Ostrava, Czech Republic

Mathematics, 2022, vol. 10, issue 20, 1-19

Abstract: In recent years, the issue of maximizing submodular functions has attracted much interest from research communities. However, most submodular functions are specified in a set function. Meanwhile, recent advancements have been studied for maximizing a diminishing return submodular (DR-submodular) function on the integer lattice. Because plenty of publications show that the DR-submodular function has wide applications in optimization problems such as sensor placement impose problems, optimal budget allocation, social network, and especially machine learning. In this research, we propose two main streaming algorithms for the problem of maximizing a monotone DR-submodular function under cardinality constraints. Our two algorithms, which are called StrDRS 1 and StrDRS 2 , have ( 1 / 2 ? ? ) , ( 1 ? 1 / e ? ? ) of approximation ratios and O ( n ? log ( log B ? ) log k ) , O ( n ? log B ) , respectively. We conducted several experiments to investigate the performance of our algorithms based on the budget allocation problem over the bipartite influence model, an instance of the monotone submodular function maximization problem over the integer lattice. The experimental results indicate that our proposed algorithms not only provide solutions with a high value of the objective function, but also outperform the state-of-the-art algorithms in terms of both the number of queries and the running time.

Keywords: DR-submodular function; integer lattice; adaptive complexity; approximation algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/20/3772/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/20/3772/ (text/html)

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:gam:jmathe:v:10:y:2022:i:20:p:3772-:d:941210

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().