1
$\begingroup$

I want to prove that the following optimization problem is NP-Hard.

max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$

subject to

$x_j \in \{0,1\}\text{ } \forall j$

$\sum_{j=1}^M x_j \le T$

given

$R_{ij} \in \{0,1\}\text{ } \forall i,j$

As you can see the expression is quite unwieldy, and there does not seem to be any clear way to proceed with the reduction. I tried variants of Knapsack (which seemed closest), as well as other standard reductions but nothing seems to work very easily. The fractional form of the expression, combined with the product makes it quite hard to do reductions. Any help is appreciated!

$\endgroup$
1
  • $\begingroup$ Should there be a $\: 0 < \:$ on the other side of your inequality? $\;\;\;\;$ $\endgroup$
    – user6973
    Jun 9, 2015 at 1:47

1 Answer 1

2
$\begingroup$

Problem Clarifications

There's a few things worth mentioning about the problem you asked.

First of all, we need to make sure that the expression you are maximizing is well defined, so the denominator must be non-zero. Simply adding the constraint that $\sum_{j=1}^Mx_j \ge 1$ is enough.

Second, I'd rather not get into the problem of talking about whether an optimization problem is NP-hard, so I'm going to explicitly state a decision version of the problem and then the rest of this answer will talk about that.

For the decision problem, the following are the inputs (note: variables follow the naming scheme from the question except $G$ which I introduce here and stands for "goal"):

  • Two positive integers $N$ and $M$
  • A collection of values $R_{ij}\in\{0,1\}$ specified for every pair of $i$ and $j$ with $1 \le i \le N$ and $1 \le j \le M$
  • A positive integer $T$
  • A value $G$

And the output is yes if and only if there exists an assignment of values to the variables $x_j$ for $1 \le j \le M$ such that

  • for all $1 \le j \le M$, $x_j \in \{0,1\}$ and
  • $1 \le \sum_{j=1}^Mx_j \le T$ and
  • $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$

This problem is NP-hard

Reduction

We prove this by reduction from dominating set. The dominating set problem asks for a given graph and number $k$ whether some choice of $k$ vertices has the property that every vertex in the graph is either chosen or next to a chosen vertex.

Suppose we are given an instance of dominating set consisting of a graph $G = (V, E)$ and a number $k$.

For convenience, label the vertices of $G$ as $v_1, v_2, ..., v_{|V|}$.

Then we construct an instance of the problem in question as follows:

  • $N = M = |V|$
  • $R_{ij} = 1$ if and only if $(v_i, v_j) \in E$ or $i=j$
  • $T = k$
  • $G = 0$

Polynomial Time

Very little needs to be done in the reduction to construct the instance, so this reduction is clearly polynomial time.

Answer preserving

Every instance generated by this reduction has $G = 0$. Therefore the condition that $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$ is equivalent to the condition that for every $i$ with $1 \le i \le N$, $\sum_{j=1}^Mx_jR_{ij} \ne 0$. That in turn is equivalent to the condition that for all $i =1, ..., N$, there exists some $j \in \{1, ..., M\}$ such that $x_j = R_{ij} = 1$.

In other words, once we work in the fact that $N = M = |V|$ and $T = k$, we see that the instance is a yes instance if and only if there exists an assignment of zeros and ones to the variables $x_j$ such that

  • at least one and at most $k$ values of $j$ have $x_j = 1$ and
  • for all $i =1, ..., |V|$, there exists some $j \in \{1, ..., |V|\}$ such that $x_j = R_{ij} = 1$

That in turn is equivalent to choosing between $1$ and $k$ indices (the ones for which $x_j = 1$) such that for all $i =1, ..., |V|$, some one of the chosen indices $j$ has $R_{ij} = 1$.

But $R_{ij} = 1$ if and only if $i = j$ or $(v_i, v_j) \in E$. Thus solving the instance is equivalent to choosing between $1$ and $k$ indices from $1$ to $|V|$ such that for every $i$, either $i$ is chosen or $v_i$ is adjacent in $G$ to some $v_j$ with j chosen.

Restating this one last time, the answer to the instance generated by the reduction is the same as the answer to the following question: is it possible to choose between $1$ and $k$ vertices in $G$ such that each vertex is either chosen or adjacent to a chosen vertex. This is the original dominating set instance.

We have shown that the reduction is answer preserving, so this concludes the proof that the decision problem in question is NP-hard.

$\endgroup$
1
  • $\begingroup$ The problem you stated is in fact NP-complete, not just NP-hard. $\;$ $\endgroup$
    – user6973
    Jun 10, 2015 at 4:11

Your Answer

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

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