|国家预印本平台
首页|An Exact Solver for Maximizing a Submodular Function Subject to a Knapsack Constraint

An Exact Solver for Maximizing a Submodular Function Subject to a Knapsack Constraint

An Exact Solver for Maximizing a Submodular Function Subject to a Knapsack Constraint

来源:Arxiv_logoArxiv
英文摘要

We study the problem of maximizing a monotone increasing submodular function over a set of weighted elements subject to a knapsack constraint. Although this problem is NP-hard, many applications require exact solutions, as approximate solutions are often insufficient in practice. To address this need, we propose an exact branch-and-bound algorithm tailored for the submodular knapsack problem and introduce several acceleration techniques to enhance its efficiency. We evaluate these techniques on instances of three benchmark problems and compare the proposed solvers to two solvers by Sakaue and Ishihata, which are considered state-of-the-art, demonstrating that the presented methods outperform the existing methods.

Sabine Münch、Stephen Raach

计算技术、计算机技术

Sabine Münch,Stephen Raach.An Exact Solver for Maximizing a Submodular Function Subject to a Knapsack Constraint[EB/OL].(2025-07-22)[2025-08-18].https://arxiv.org/abs/2507.16149.点此复制

评论