Kavli Affiliate: Yi Zhou
| First 5 Authors: Yimin Hao, Yimin Hao, , ,
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=3