Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.11107 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913942625845248 |
|---|---|
| author | Hao, Yimin Zhou, Yi Xu, Chao Fu, Zhang-Hua |
| author_facet | Hao, Yimin Zhou, Yi Xu, Chao Fu, Zhang-Hua |
| contents | The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeat computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11107 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint Hao, Yimin Zhou, Yi Xu, Chao Fu, Zhang-Hua Data Structures and Algorithms The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeat computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods. |
| title | Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.11107 |