Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929350739230720 |
|---|---|
| author | Pham, Canh V. |
| author_facet | Pham, Canh V. |
| contents | In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size $n$. The problem recently attracted a lot of attention due to its applications in various domains of combination optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from $6+ε$ to $5+ε$ while keeping the best query complexity of $O(n)$, where $ε>0$ is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12252 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity Pham, Canh V. Data Structures and Algorithms Artificial Intelligence In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size $n$. The problem recently attracted a lot of attention due to its applications in various domains of combination optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from $6+ε$ to $5+ε$ while keeping the best query complexity of $O(n)$, where $ε>0$ is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor. |
| title | Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2405.12252 |