Weapon target assignment leveraging strong submodularity

Optimal weapon target assignment problem involves NP-complete searching process and becomes computationally impractical as the number of weapons and targets increases. Existing approaches, therefore, only consider approximate method with heuristic searching scenarios, which are, however, no theoretical performance guarantee for the level of accuracy that the underlying algorithm may achieve. In this paper, the weapon target assignment problem is studied in the framework of combinatorial optimization theory. Following a previous work, an accelerated continuous greedy algorithm is proposed to address the underlying problem in polynomial time. The algorithm is proved to have the best guaranteed performance against optimal solution among the existing polynomial time methods.