# Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2017.

## Built on by (most cited first, 4 of 4)

- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Localized Distributional Robustness in Submodular Multi-Task Subset Selection](https://mlsanity.com/paper/2404.03759/) (2024)
- [Revisiting Matching Pursuit: Beyond Approximate Submodularity](https://mlsanity.com/paper/2305.07782/) (2023)

## Abstract (arXiv)

We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max|A|=kmin_i∈1,dots,mfi(A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, Krause et al. (2008) showed that when the number of objectives m grows as the cardinality k i.e., m=Omega(k), the problem is inapproximable (unless P=NP). On the other hand, when m is constant Chekuri et al. (2010) showed a randomized (1-1/e)-ε approximation with runtime (number of queries to function oracle) nm/ε3. %In fact, the result of Chekuri et al. (2010) is for the far more general case of matroid constant. We focus on finding a fast and practical algorithm that has (asymptotic) approximation guarantees even when m is super constant. We first modify the algorithm of Chekuri et al. (2010) to achieve a (1-1/e) approximation for m=o(fracklog3 k). This demonstrates a steep transition from constant factor approximability to inapproximability around m=Omega(k). Then using Multiplicative-Weight-Updates (MWU), we find a much faster tildeO(n/δ3) time asymptotic (1-1/e)2-δ approximation. While the above results are all randomized, we also give a simple deterministic (1-1/e)-ε approximation with runtime knm/ε4. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.