NobleBlocks

Research indexJournal article

A Priority-Ordered Swapping Algorithm for Submodular Maximization Problems

Peng, Meng, Li

IEEE Control Systems Letters1 Jan 2026Open access

NobleIDark:/48914/w1/20261006/2679F1F8DOI10.1109/lcsys.2026.3670932

Abstract

In this paper, we delve into the monotone sub-modular maximization problem with a cardinality constraint. We propose a priority-ordered swapping algorithm that iteratively improves the solution by swapping the lowest priority elements in the current solution set with elements from the ground set. This algorithm can effectively complement the greedy approach, especially when starting from the greedy solution. Moreover, we quantify the performance gap between our algorithm’s solution and the optimal solution, providing a theoretical guarantee for its effectiveness. We also identify conditions under which our algorithm outperforms standard greedy approaches in terms of approximation quality. In addition, the effectiveness of the proposed algorithm is further demonstrated by applying it to the multi-agent coverage problem.

Discussion

Citations

Topics

More

Suggest a correction or report