We study the deletion robust version of submodular maximization under matroid constraints. The goal is to extract a small-size summary of the data set that contains a high-value independent set even after an adversary deletes some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank k of the matroid, the number d of deleted elements, and the input precision ε.
Deletion Robust Non-Monotone Submodular Maximization over Matroids / Dütting, P.; Fusco, F.; Lattanzi, S.; Norouzi-Fard, A.; Zadimoghaddam, M.. - In: JOURNAL OF MACHINE LEARNING RESEARCH. - ISSN 1532-4435. - 26:(2025), pp. 1-28.
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Fusco F.;Lattanzi S.;
2025
Abstract
We study the deletion robust version of submodular maximization under matroid constraints. The goal is to extract a small-size summary of the data set that contains a high-value independent set even after an adversary deletes some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank k of the matroid, the number d of deleted elements, and the input precision ε.| File | Dimensione | Formato | |
|---|---|---|---|
|
Dutting_Deletion-Robust_2025.pdf
accesso aperto
Note: https://www.jmlr.org/papers/v26/23-1219.html
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
406.58 kB
Formato
Adobe PDF
|
406.58 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
