"Bring Your Own Greedy"+Max: Near-Optimal $1/2$-Approximations for Submodular Knapsack
This work addresses efficient data summarization for applications like recommendation systems, offering incremental improvements in approximation guarantees across offline, streaming, and distributed settings.
The authors tackled the problem of selecting a small representative summary from large datasets under a knapsack constraint, proposing a new algorithmic framework that achieves near-optimal 1/2-approximations with instance-specific results often exceeding 0.6-0.7, beating the 0.63 worst-case barrier.
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to recommendation systems and other scenarios with query-limited access to vast amounts of data, we propose a new rigorous algorithmic framework for a standard formulation of this problem as a submodular maximization subject to a linear (knapsack) constraint. Our framework is based on augmenting all partial Greedy solutions with the best additional item. It can be instantiated with negligible overhead in any model of computation, which allows the classic \greedy algorithm and its variants to be implemented. We give such instantiations in the offline (Greedy+Max), multi-pass streaming (Sieve+Max) and distributed (Distributed+Max) settings. Our algorithms give ($1/2-ε$)-approximation with most other key parameters of interest being near-optimal. Our analysis is based on a new set of first-order linear differential inequalities and their robust approximate versions. Experiments on typical datasets (movie recommendations, influence maximization) confirm scalability and high quality of solutions obtained via our framework. Instance-specific approximations are typically in the 0.6-0.7 range and frequently beat even the $(1-1/e) \approx 0.63$ worst-case barrier for polynomial-time algorithms.