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

CREATORAlan Kuhnle
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.04428

Browse the full library · About the Tower of Babel