Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query Complexity

Suning Gong (), Qingqin Nong (), Jiazhu Fang () and Ding-Zhu Du ()
Additional contact information
Suning Gong: Qingdao University
Qingqin Nong: Ocean University of China
Jiazhu Fang: Ocean University of China
Ding-Zhu Du: University of Texas

Journal of Optimization Theory and Applications, 2024, vol. 200, issue 1, No 7, 194-214

Abstract: Abstract Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries.

Keywords: DR-submodular maximization; Cardinality constraint; Design and analysis of approximation algorithms; 90C27; 68W25; 68W40 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-023-02353-7 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:joptap:v:200:y:2024:i:1:d:10.1007_s10957-023-02353-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-023-02353-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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