Weapon target assignment problem: Difference between revisions

Revision as of 02:16, 11 June 2011

Revision as of 02:34, 11 June 2011

Line 26:

== Algorithms and generalizations ==

It has long been known that assignment problems are [[NP-hard]]. Nonetheless, an exact solution can be found using [[branch and bound]] techniques which utilize [[relaxation (approximation}]]. Many heuristic algorithms have been proposed which provide near-optimal solutions in [[polynomial time]] <ref>Ahuja, R. et al. Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem. Operations Research 55(6), pp. 1136–1146, 2007</ref>.

The weapon target assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the [[quadratic assignment problem]].

==Example==

Line 43:

==See also==

*[[Stable marriage problem]]

*[[Auction algorithm]]

*[[Generalized assignment problem]]

*[[Linear bottleneck assignment problem]]

*[[Quadratic assignment problem]]

*[[Stable marriage problem]]

== Further reading ==

Line 64:

== References ==

<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->

{{Reflist}}