Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
Alan Kuhnle · 2026
Read Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation by Alan Kuhnle (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04428.txt.
Description
Alan Kuhnle studies a preprocessing step for large subset-selection problems, such as choosing examples, features, or sensors from an enormous pool. The idea is to prune the pool to a smaller core first. The core must still contain a near-best feasible selection. That guarantee must hold for every budget up to a given size.
For monotone objectives with diminishing returns, Kuhnle proves the classic greedy factor is the best any pruning method can guarantee, even with a larger budget. For non-monotone objectives, he gives the first algorithms with a factor near one half. They work under size and knapsack limits. They even beat the known ratios for the maximisation problem itself.
Catalog record
| CREATOR | Alan Kuhnle |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 122 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04428