Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint [Accepted to NeurIPS'24]

1 DataHeroes | 2 University of Haifa

Murad Tukan, Loay Mualem, and Moran Feldman

We kindly refer you to our paper:

• This work introduces a novel combinatorial algorithm for maximizing a non-negative submodular function subject to a cardinality constraint.
• Our suggested method combines a practical query complexity of $O(n + k^2)$ with an approximation guarantee of $0.385$, which improves over the $\frac{1}{e}$-approximation of the state-of-the-art practical algorithm.

In this repository, we present our submodular maximization optimization code (tested with Python 3.11).

Citation

If you find this work helpful please cite us:

@article{tukan2024practical,

title={Practical $0.385 $-Approximation for Submodular Maximization Subject to a Cardinality Constraint},

author={Tukan, Morad and Mualem, Loay and Feldman, Moran},

journal={Advances in Neural Information Processing Systems},

volume={37},

pages={51223--51253},

year={2024}