# Covering a Few Submodular Constraints and Applications

arXiv: https://arxiv.org/abs/2507.09879 · HTML: https://mlsanity.com/paper/2507.09879/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 38 references that are in the map.
- First posted on arXiv 14 Jul 2025.

## Builds on (most cited first, 9 of 9)

- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [A Constant Approximation for Colorful k-Center](https://mlsanity.com/paper/1907.08906/) (2019)
- [On Approximating (Sparse) Covering Integer Programs](https://mlsanity.com/paper/1807.11538/) (2018)
- [Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii](https://mlsanity.com/paper/2412.16327/) (2024)
- [Partial resampling to approximate covering integer programs](https://mlsanity.com/paper/1507.07402/) (2015)
- [On Partial Covering For Geometric Set Systems](https://mlsanity.com/paper/1711.04882/) (2017)
- [Few Cuts Meet Many Point Sets](https://mlsanity.com/paper/1808.03260/) (2018)
- [Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints](https://mlsanity.com/paper/2308.04846/) (2023)

## Abstract (arXiv)

We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N rightarrow ℝ_+, r monotone submodular functions f1,f2,ldots,fr over N and requirements b1,b2,ldots,br the goal is to find a minimum cost subset S subseteq N such that fi(S) ≥ bi for 1 ≤ i ≤ r. When r=1 this is the well-known Submodular Set Cover problem. Previous work citechekuri2022covering considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each fi is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Omega(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. For covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that fi(S) ≥ (1-1/eα -ε)bi for each i ∈ [r] and mathbbE[c(S)] ≤ (1+ε)α · sfOPT. Second, when the fi are weighted coverage functions from a deletion-closed set system we obtain a (1+ε) (fracee-1) (1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r=1. We mention some applications that follow easily from these general results and anticipate more in the future.