An Efficient Approximation for Weapon-Target Assignment

The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. We present firstly a technique founded on the use weapon cell, which enables one-to-many mapping about weapon-target to become one-to-one mapping. Next, we introduce a framework of solving the WTA problem. Based on this framework, an approximation algorithm that is grounded on the rules about weapon cells and targets is proposed. Finally, the simulative results show that the proposed algorithm indeed is very efficient.