5
$\begingroup$

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

$\endgroup$
8
  • 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$ Sep 20, 2013 at 19:59
  • 2
    $\begingroup$ I've always disliked this problem. We're not working for the army. $\endgroup$ Sep 21, 2013 at 0:41
  • $\begingroup$ your local library might retrieve this document for you $\endgroup$ Sep 21, 2013 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, 2013 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$ Sep 24, 2013 at 1:50

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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