License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.41
URN: urn:nbn:de:0030-drops-173263
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17326/
Qi, Benjamin
On Maximizing Sums of Non-Monotone Submodular and Linear Functions
Abstract
We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by [Bodek and Feldman '22]. In this problem, we are given query access to a non-negative submodular function f: 2^N → ℝ_{≥ 0} and a linear function 𝓁: 2^N → ℝ over the same ground set N, and the objective is to output a set T ⊆ N approximately maximizing the sum f(T)+𝓁(T). Specifically, an algorithm is said to provide an (α,β)-approximation for RegularizedUSM if it outputs a set T such that E[f(T)+𝓁(T)] ≥ max_{S ⊆ N}[α ⋅ f(S)+β⋅ 𝓁(S)]. We also study the setting where S and T are constrained to be independent in a given matroid, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM).
The special case of RegularizedCSM with monotone f has been extensively studied [Sviridenko et al. '17, Feldman '18, Harshaw et al. '19]. On the other hand, we are aware of only one prior work that studies RegularizedCSM with non-monotone f [Lu et al. '21], and that work constrains 𝓁 to be non-positive. In this work, we provide improved (α,β)-approximation algorithms for both {RegularizedUSM} and {RegularizedCSM} with non-monotone f. In particular, we are the first to provide nontrivial (α,β)-approximations for RegularizedCSM where the sign of 𝓁 is unconstrained, and the α we obtain for RegularizedUSM improves over [Bodek and Feldman '22] for all β ∈ (0,1).
In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the α our algorithm obtains for {RegularizedCSM} with unconstrained 𝓁 is essentially tight for β ≥ e/(e+1). Using similar ideas, we are also able to show 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to [Oveis Gharan and Vondrak '10].
BibTeX - Entry
@InProceedings{qi:LIPIcs.ISAAC.2022.41,
author = {Qi, Benjamin},
title = {{On Maximizing Sums of Non-Monotone Submodular and Linear Functions}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {41:1--41:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17326},
URN = {urn:nbn:de:0030-drops-173263},
doi = {10.4230/LIPIcs.ISAAC.2022.41},
annote = {Keywords: submodular maximization, regularization, continuous greedy, inapproximability}
}
