2
$\begingroup$

Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note. This problem is studied in wireless communication where the set represents links in a wireless network, the $P_i$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example here, but the reduction is very hard for me.

$\endgroup$
  • $\begingroup$ If ​ 0 < $\epsilon$ ​ then the denominator will necessarily be strictly positive, in which case that inequality can be simplified. ​ ​ ​ ​ $\endgroup$ – user12859 Feb 13 '16 at 0:30
  • $\begingroup$ Are you sure it is $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$ and not $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\leq 1,\text{ for all } i \in S.$ or something like $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq \lambda,\text{ for all } i \in S.$ $\endgroup$ – Shreesh Feb 13 '16 at 7:10
1
$\begingroup$

This problem can be solved in polynomial time. Therefore, it's likely not NP-hard (unless P = NP).

After a little bit of algebraic manipulation, we find that the condition on $S$ is equivalent to requiring that

$$2 P_i \ge \varepsilon + \sum_{j \in S} P_j \quad \text{for all $i \in S$}.$$

This, in turn, is equivalent to requiring

$$2 \min \{P_i : i \in S\} \ge \varepsilon + \sum_{j \in S} P_j.$$

For convenience, sort the $P_i$'s into increasing order, so $P_1 \le P_2 \le \dots \le P_n$.

Now one can prove that if there is any set of cardinality $k$ that satisfies this equation, then there's a set of the form $S = \{t,t+1,t+2,\dots,t+k-1\}$ that satisfies this equation, for some $t$. (This can be proven using an exchange argument, swapping pairs of indices as needed and showing that the swap leaves the left-hand side unchanged and only decreases the right-hand side.)

Now you can try all possible values of $t$ and see whether the corresponding set satisfies the condition. There are only $n$ possible values of $t$, so this can certainly be tested in polynomial time. In fact, with clever programming (prefix sums, etc.), you can implement this in $O(n \lg n)$ time, or in $O(n)$ time if the $P_i$'s are already provided in sorted order.


More generally, if you want to find the set $S$ of maximum cardinality that satisfies the equation, such a set will have the form $S=\{t,t+1,t+2,t+3,\dots,u\}$ for some $t,u$. Therefore, you can try all such possibilities and see which has largest cardinality. This too can be done in $O(n \lg n)$ time using appropriate methods (binary search, prefix sums). Alternatively, you can do binary search on $k$, and apply the decision algorithm of the previous paragraph for each candidate value of $k$ to find the largest $k$ for which a solution exists. The running time is again $O(n \lg n)$.

$\endgroup$
1
$\begingroup$

In equation $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$, and positive $\epsilon > 0$ we can never have $k \geq 2$. Even in the case $k=2$ either $2P_1 < \epsilon + P_1 + P_2$ or $2P_2 < \epsilon + P_1 + P_2$.

And for $k = 1$ every subset is a yes-instance for small enough $\epsilon$.

So the problem is trivially polynomial.

$\endgroup$
  • $\begingroup$ Thank you for your comments. If there is $\lambda$ as you said in the definition of the problem, can you see how it is NP-hard? $\endgroup$ – Chiba Feb 13 '16 at 10:57
  • $\begingroup$ No, it seems it will be in $P$. $\endgroup$ – Shreesh Feb 13 '16 at 11:35
  • $\begingroup$ The statement "Even in the case $k=2$ either $2P_1<\epsilon+P_1+P_2$ or $2P_2<\epsilon+P_1+P_2$" is not correct. Take $P_1=10,P_2=1,\epsilon=10$. You have $20<10+10+1$ and $2<10+10+1$. $\endgroup$ – Chiba Feb 16 '16 at 22:55
  • $\begingroup$ Why? 20 < 10+ 10+1! I said "OR" and not "AND". $\endgroup$ – Shreesh Feb 17 '16 at 5:11

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.