Deletion Robust Non-Monotone Submodular Maximization over Matroids
Authors: Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
JMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 ε. In the centralized setting we present a (4.494 + O(ε))-approximation algorithm with summary size O( k+d ε ) that improves to a (3.582 + O(ε))-approximation with O(k + d ε ) summary size when the objective is monotone. |
| Researcher Affiliation | Collaboration | Paul Dütting EMAIL Google Research, Zurich, Switzerland; Federico Fusco EMAIL Department of Computer, Control and Management Engineering Antonio Ruberti Sapienza University of Rome Rome, Italy |
| Pseudocode | Yes | Algorithm 1 Centralized Algorithm Phase I; Algorithm 2 Algorithm Phase II; Algorithm 3 Streaming Algorithm Phase I |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments using specific datasets. It mentions application areas such as 'movie recommendation' but does not provide details or access information for any dataset used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments using specific datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and approximation guarantees, without describing any experimental setup, hyperparameters, or system-level training settings. |