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".

  • 4
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 20 '13 at 19:59
  • 2
    $\begingroup$ I've always disliked this problem. We're not working for the army. $\endgroup$ – Yuval Filmus Sep 21 '13 at 0:41
  • $\begingroup$ your local library might retrieve this document for you $\endgroup$ – Austin Buchanan Sep 21 '13 at 2:45
  • $\begingroup$ this is a thesis on this topic and briefly described the proof technique of NP-completeness of problem. $\endgroup$ – Saeed Sep 21 '13 at 11:47
  • 2
    $\begingroup$ @Saeed: The direction is wrong. One needs to formulate a NP-complete problem as the weapon-target assignment problem. $\endgroup$ – Yoshio Okamoto Sep 24 '13 at 1:50

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] ):


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.