Papers › Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem
Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem
Jianrong Zhou, Jiongzhi Zheng, Kun He
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We address the Budgeted Maximum Coverage Problem (BMCP), which is a natural and more practical extension of the standard 0-1 knapsack problem and the set cover problem. Given m elements with nonnegative weights, n subsets of elements with nonnegative costs, and a total budget, BMCP aims to select some subsets such that the total cost of selected subsets does not exceed the budget, and the total weight of associated elements is maximized. In this paper, we propose a variable depth local search algorithm (VDLS) for the BMCP. VDLS first generates an initial solution by a greedy algorithm, then iteratively improves the solution through a partial depth-first search method, that can improve the solution by simultaneously changing the states (selected or not) of multiple subsets. Such method allows VDLS to explore the solution space widely and deeply, and to yield high-quality solutions. We further propose a neighbour structure to boost the algorithm performance, that is, both subsets have a neighbour relation if they have at least one common associated element. By applying the neighbour structure, VDLS can adjust the selected subsets while losing as few covered elements as possible. Since the existing BMCP benchmarks only have simple structures and small scales, we design 60 new instances with relatively large scales and complex structures to enrich the diversity of the BMCP instances. Experimental results on 30 public instances and 60 new instances we designed demonstrate that VDLS significantly outperforms the existing heuristic and the general CPLEX exact solver, for the BMCP.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections