Revisiting non-monotone regularized submodular maximization: bi-criteria and PASS approximations

Cheng Lu ()
Additional contact information
Cheng Lu: University of Chinese Academy of Sciences

Journal of Global Optimization, 2025, vol. 92, issue 2, No 9, 453-481

Abstract: Abstract We study the problem of maximizing the difference between a non-monotone submodular function and a modular function. We adopt the convention in the literature and refer to this problem as the non-monotone Regularized Submodular Maximization (RSM) problem. Since the RSM problem is inapproximable, our goal is to design algorithms which are guaranteed to provide the bi-criteria and PASS approximations. For the cardinality-constrained problem, we propose two algorithms: one is based on the maximization of a scaled objective function, and the other one is a refinement of the algorithm given in our previous paper. Our analysis shows that both algorithms have nontrivial approximation bounds. For the matroid-constrained problem, we also design an algorithm based on the scaled function technique. Although its approximation guarantee is weaker than the existing algorithms in the literature, it requires less function evaluations which makes it more practical in applications.

Keywords: Regularized submodular maximization; Greedy algorithm; Bi-criteria approximation; PASS approximation; 90C27; 90C59; 68Q25 (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01473-w 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:92:y:2025:i:2:d:10.1007_s10898-025-01473-w

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

DOI: 10.1007/s10898-025-01473-w

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 ().