# Weapon target assignment problem

Does anybody know a NP-hardness proof of Weapon-target assignment problem (http://en.wikipedia.org/wiki/Weapon_target_assignment_problem)? Lloyd and Witsenhausen produced a reduction from 3-EXACT-COVER, but it seems that there is no chance to get their paper titled "Weapons allocation is NP-complete".

• If you can't get it any other way, Amazon.com will sell you a copy of the conference proceedings (1986 Summer Conference on Simulation, Reno, NV) for $42. The conference was run by what is now The Society for Modeling & Simulation International, who may also be able to help. – David Richerby Sep 20 '13 at 19:59 • I've always disliked this problem. We're not working for the army. – Yuval Filmus Sep 21 '13 at 0:41 • your local library might retrieve this document for you – Austin Buchanan Sep 21 '13 at 2:45 • this is a thesis on this topic and briefly described the proof technique of NP-completeness of problem. – Saeed Sep 21 '13 at 11:47 • @Saeed: The direction is wrong. One needs to formulate a NP-complete problem as the weapon-target assignment problem. – Yoshio Okamoto Sep 24 '13 at 1:50 ## 1 Answer I don't have access to the original paper, but this is an alternate reduction from SUBSET PRODUCT. The decision version of the WEAPON TARGET ASSIGNMENT (WTA) problem is: Input: Given an integer$k$,$W_i$weapons of type$i = 1,...,m$,$n$targets$j=1,...,n$having values$V_j$; each weapon type has a certain probability of destroying each target, given by$p_{i,j}$. Question: Does there exist an assignment of the available weapons such that: $$D = \sum_{j=1}^n V_j \prod_{i=1}^m q_{i,j}^{x_{i,j}} \leq k$$ where$x_{i,j} = 1$if weapon$i$is assigned to target$j$($x_{i,j} = 0$otherwise), and$q_{i,j} = 1 - p_{i,j}$(survival probability of target$j$when hit by weapon$i$). Given a set of positive integers$A= \{a_1, a_2, ..., a_m\}$, and a target product$b$; the SUBSET PRODUCT problems asks for a subset$X \subseteq \{1,2,...,m\}$such that$\prod_{i \in X} a_i = b$. Let$P = \prod a_i$, note that if$b \nmid P$then the subset product problem doesn't have a solution. We can build a WTA instance with two targets ($n=2$) having the same value$V_1 = V_2= P$and$m+2$weapons$W_1,W_2,...,W_m,W_{\alpha},W_{\beta}$: • weapons$W_1,W_2,...,W_m$can destroy both targets with probability$p_{i,1} = p_{i,2} = 1 - \frac{1}{a_i}$(the survival probability is$q_{i,1} = q_{i,2} = \frac{1}{a_i}$); • weapon$W_{\alpha}$can destroy both targets with probability$p_{i,1} = p_{i,2} = 1 - \frac{b}{2P}$(the survival probability is$q_{i,1} = q_{i,2} = \frac{b}{2P}$); • weapon$W_{\beta}$can destroy both targets with probability$p_{i,1} = p_{i,2} = 1 - \frac{1}{2b}$(the survival probability is$q_{i,1} = q_{i,2} = \frac{1}{2b})$We set$k = 1$. ($\Rightarrow$) Suppose that the original subset sum problem has a solution$X$; let$Y=\{1,\ldots,m\} \setminus X$. Then $$\prod_{i \in X} \frac{1}{a_i}=\frac{1}{b},\quad \prod_{y \in Y} \frac{1}{a_y} = \frac{b}{P}$$ If we assign weapons$W_x, x \in X$and$W_{\alpha}$to target 1; weapons$W_y, y \in Y$and$W_{\beta}$to target 2 we get: $$D= V_1 * \frac{b}{2P}* \frac{1}{b} + V_2 * \frac{1}{2b}* \frac{b}{P} = P * \frac{b}{2P}* \frac{1}{b} + P * \frac{1}{2b}* \frac{b}{P} = 1$$ ($\Leftarrow$) Suppose that the WTA instance has a solution and let$X',Y'$be the indices of the weapons assigned to target 1 and 2 respectively ($X',Y'\subseteq \{1,\ldots,m,\alpha,\beta\}$). We must have: $$D = P \prod_{x \in X'} q_{x,1} + P \prod_{y \in Y'} q_{y,2} \leq 1$$$W_{\alpha}$and$W_{\beta}$cannot both belong to$X'$(or$Y'$), otherwise: $$P \frac{1}{2b}*\frac{b}{2P}*\frac{1}{ \prod_{x \in X'\setminus \{\alpha,\beta\}} a_x} + \frac{P}{ \prod_{y \in Y'} a_y} \geq \frac{1}{4 \prod_{x \in X'\setminus \{\alpha,\beta\}} a_x}+1 > 1$$ So suppose that weapon$W_{\alpha}$is assigned to target 1 and$W_{\beta}$to target 2; let$X = X' \setminus \{ \alpha \}, Y = Y' \setminus \{ \beta \}$; we must have: $$P \frac{b}{2P} \prod_{x \in X} \frac{1}{a_x} + P\frac{1}{2b} \prod_{y \in Y} \frac{1}{a_y} \leq 1$$ $$\mbox{if } z = \prod_{x \in X} a_x, \quad \frac{b}{2z} + \frac{z}{2b} \leq 1$$ Multiplying both sides by the positive quantity$2bz$we get: $$b^2 + z^2 \leq 2bz$$ $$(b - z)^2 \leq 0$$ So we must have$b = z = \prod_{x \in X} a_x$, so$X\$ is a valid solution for the original SUBSET PRODUCT problem.

(P.S. Unfortunately, despite the hardness of this problem, the war between peoples seems to be a lot easier to start ..."The day the power of love overrules the love of power, the world will know peace." [Mahatma Gandhi] ):