.png){kind=icon}
.png){kind=icon}
Return
A Priority-Ordered Swapping Algorithm for Submodular Maximization Problems
.png){kind=icon}
PRE
AI
P
M
L
DOI：10.1109/LCSYS.2026.3670932.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this letter, we delve into the monotone submodular 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.
Keywords:
Greedy algorithms
Approximation algorithms
Finite element analysis
Linear programming
Sorting
Partitioning algorithms
Convergence
Computational complexity
Silicon
Optimization
Coverage control
multi-agent systems
optimization
submodular maximization
Journal
I
IF:
2
Papers:
94
Citations:
5.0K
Organization
Cited Papers