Efficient Branch-and-Bound for Submodular Maximization under Knapsack Constraint

Yimin Hao, Yi Zhou, Chao Xu, Zhang-Hua Fu

University of Electronic Science and Technology of China, \ Shenzhen Institute of Artificial Intelligence and Robotics for Society

Abstract

We study the Submodular Knapsack Problem (SKP) — maximizing a monotone submodular function under a budget. We propose an exact branch-and-bound method with a refined subset upper bound (tight worst-case guarantee) and a dual branching strategy that halves repeated computations. On canonical applications (facility location, weighted coverage, influence maximization, partial dominating set), our method significantly outperforms existing exact solvers.

---

Why it matters

Submodular maximization models real decisions with diminishing returns (e.g., health-care facility location, risk-sensitive planning, influence maximization). In many high-stakes settings, optimality is crucial—approximate solutions can be insufficient. Hence the need for fast exact algorithms.

---

Highlights

• Refined Subset Bound (RS) A new upper bound that leverages the greedy expansion sequence; theoretically ≤ 1/(1−e⁻¹) ≈ 1.582× OPT when weights are small vs. budget, and empirically tighter than prior bounds (domination / fractional-knapsack).

• Dual Branching Method Reuses marginal-gain computations from greedy steps, avoiding recomputation across sibling nodes; ~2× average speed-up vs. basic branching.

• Practical wins Across 200 instances, dual-rs delivers the best overall runtime and visits the fewest nodes (especially on DOM). Competes strongly with or beats prior exact solvers (A* variants, ILP) and leading cardinality-specialized combinatorial solvers.

---

Experimental results

Benchmarks

Four standard submodular problems:

1. Weighted Coverage (COV)
2. Influence Maximization (INF)
3. Facility Location (LOC)
4. Partial Dominating Set (DOM)

Performance comparison

Comparison of solver performance across the benchmark datasets.

---

Code and Data Link

---

Citation

If you use this work, please cite:

@misc{hao2025efficientbranchandboundsubmodularfunction,
      title={Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint}, 
      author={Yimin Hao and Yi Zhou and Chao Xu and Zhang-Hua Fu},
      year={2025},
      eprint={2507.11107},
      archivePrefix={arXiv},
      primaryClass={cs.DS},
      url={https://arxiv.org/abs/2507.11107}, 
}

Read the paper on arXiv.

---

Last updated: October 2025

---