A Priority-Ordered Swapping Algorithm for Submodular Maximization Problems

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.