Practical $0385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
<|reference_start|>Practical $0385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint: Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications. However, existing algorithms often struggle with a trade-off between approximation guarantees and practical efficiency. The current state-of-the-art is a recent $0.401$-approximation algorithm, but its computational complexity makes it highly impractical. The best practical algorithms for the problem only guarantee $1/e$-approximation. In this work, we present a novel algorithm for submodular maximization subject to a cardinality constraint that combines a guarantee of $0.385$-approximation with a low and practical query complexity of $O(n+k^2)$. Furthermore, we evaluate the empirical performance of our algorithm in experiments based on various machine learning applications, including Movie Recommendation, Image Summarization, and more. These experiments demonstrate the efficacy of our approach.<|reference_end|>
@article{tukan2024practical,
    title={Practical $0.385$-Approximation for Submodular Maximization Subject to a
  Cardinality Constraint},
    author={Murad Tukan, Loay Mualem, Moran Feldman},
    journal={arXiv preprint arXiv:2405.13994},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13994},
    primaryClass={cs.LG cs.DM cs.DS}
}