Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911884799639552 |
|---|---|
| author | Tukan, Murad Mualem, Loay Feldman, Moran |
| author_facet | Tukan, Murad Mualem, Loay Feldman, Moran |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13994 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint Tukan, Murad Mualem, Loay Feldman, Moran Machine Learning Discrete Mathematics Data Structures and Algorithms 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. |
| title | Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint |
| topic | Machine Learning Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.13994 |