Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911519282823168 |
|---|---|
| author | Chen, Shengminjie Gao, Yiwei Lin, Kaifeng Sun, Xiaoming Zhang, Jialin |
| author_facet | Chen, Shengminjie Gao, Yiwei Lin, Kaifeng Sun, Xiaoming Zhang, Jialin |
| contents | Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. Under matroid constraints, our algorithm achieves an approximation ratio of $(0.385 - ε)$, whereas for knapsack constraints, the proposed algorithm attains an approximation ratio of $(0.367 -ε)$. Both algorithms run in $\mathrm{poly}(n)$ query complexity, where $n$ is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of $(0.367 - ε)$ for matroid constraints and $0.25$ for knapsack constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11996 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints Chen, Shengminjie Gao, Yiwei Lin, Kaifeng Sun, Xiaoming Zhang, Jialin Data Structures and Algorithms Computational Complexity Optimization and Control Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. Under matroid constraints, our algorithm achieves an approximation ratio of $(0.385 - ε)$, whereas for knapsack constraints, the proposed algorithm attains an approximation ratio of $(0.367 -ε)$. Both algorithms run in $\mathrm{poly}(n)$ query complexity, where $n$ is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of $(0.367 - ε)$ for matroid constraints and $0.25$ for knapsack constraints. |
| title | Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints |
| topic | Data Structures and Algorithms Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2603.11996 |