Robust monotone submodular function maximization
Abstract We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42:427–486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131367 |
| _version_ | 1826197242268090368 |
|---|---|
| author | Orlin, James B Schulz, Andreas S Udwani, Rajan |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Orlin, James B Schulz, Andreas S Udwani, Rajan |
| author_sort | Orlin, James B |
| collection | MIT |
| description | Abstract
We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42:427–486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to
$$\tau $$
τ
elements from the chosen set. For the fundamental case of
$$\tau =1$$
τ
=
1
, we give a deterministic
$$(1-1/e)-1/\varTheta (m)$$
(
1
-
1
/
e
)
-
1
/
Θ
(
m
)
approximation algorithm, where m is an input parameter and number of queries scale as
$$O(n^{m+1})$$
O
(
n
m
+
1
)
. In the process, we develop a deterministic
$$(1-1/e)-1/\varTheta (m)$$
(
1
-
1
/
e
)
-
1
/
Θ
(
m
)
approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (in: FOCS 10, IEEE, pp 575–584, 2010), we show a randomized
$$(1-1/e)-\epsilon $$
(
1
-
1
/
e
)
-
ϵ
approximation for constant
$$\tau $$
τ
and
$$\epsilon \le \frac{1}{\tilde{\varOmega }(\tau )}$$
ϵ
≤
1
Ω
~
(
τ
)
, making
$$O(n^{1/\epsilon ^3})$$
O
(
n
1
/
ϵ
3
)
queries. Further, for
$$\tau \ll \sqrt{k}$$
τ
≪
k
, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System. |
| first_indexed | 2024-09-23T10:44:41Z |
| format | Article |
| id | mit-1721.1/131367 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:44:41Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1313672023-12-13T15:54:37Z Robust monotone submodular function maximization Orlin, James B Schulz, Andreas S Udwani, Rajan Sloan School of Management Abstract We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42:427–486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to $$\tau $$ τ elements from the chosen set. For the fundamental case of $$\tau =1$$ τ = 1 , we give a deterministic $$(1-1/e)-1/\varTheta (m)$$ ( 1 - 1 / e ) - 1 / Θ ( m ) approximation algorithm, where m is an input parameter and number of queries scale as $$O(n^{m+1})$$ O ( n m + 1 ) . In the process, we develop a deterministic $$(1-1/e)-1/\varTheta (m)$$ ( 1 - 1 / e ) - 1 / Θ ( m ) approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (in: FOCS 10, IEEE, pp 575–584, 2010), we show a randomized $$(1-1/e)-\epsilon $$ ( 1 - 1 / e ) - ϵ approximation for constant $$\tau $$ τ and $$\epsilon \le \frac{1}{\tilde{\varOmega }(\tau )}$$ ϵ ≤ 1 Ω ~ ( τ ) , making $$O(n^{1/\epsilon ^3})$$ O ( n 1 / ϵ 3 ) queries. Further, for $$\tau \ll \sqrt{k}$$ τ ≪ k , we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System. 2021-09-20T17:16:45Z 2021-09-20T17:16:45Z 2018-09-15 2020-09-24T21:02:04Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131367 en https://doi.org/10.1007/s10107-018-1320-2 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Orlin, James B Schulz, Andreas S Udwani, Rajan Robust monotone submodular function maximization |
| title | Robust monotone submodular function maximization |
| title_full | Robust monotone submodular function maximization |
| title_fullStr | Robust monotone submodular function maximization |
| title_full_unstemmed | Robust monotone submodular function maximization |
| title_short | Robust monotone submodular function maximization |
| title_sort | robust monotone submodular function maximization |
| url | https://hdl.handle.net/1721.1/131367 |
| work_keys_str_mv | AT orlinjamesb robustmonotonesubmodularfunctionmaximization AT schulzandreass robustmonotonesubmodularfunctionmaximization AT udwanirajan robustmonotonesubmodularfunctionmaximization |