3
$\begingroup$

We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum = $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2 - 1$ and weight at most $W/2$.

If the profit must be at least $P/2$, we can set the profits to be equal to the weights and reduce from the partition problem to show NP-hardness. With the requirement of profit slightly lowered to $P/2-1$, I think the problem should remain NP-hard, but the reduction doesn't work anymore. Is there a way to modify the reduction to work?

$\endgroup$

1 Answer 1

2
+50
$\begingroup$

Let $\mathcal{I}$ be an instance of the problem with profit requirement at least $P(\mathcal{I})/2$, where $P(\mathcal{I}) = p_1+\dotsc+p_{3n}$. By the previous reduction, we know that the problem is $\mathsf{NP}$-hard. Moreover, the reduced hard instances had profits $p_i$ as non-negative integers. We will exploit this fact for our reduction.

We reduce the instance $\mathcal{I}$ to an instance $\mathcal{I}'$ with profit requirement at least $P(\mathcal{I}')/2-1$. The instance $\mathcal{I}'$ is the same as instance $\mathcal{I}$ but with each profit four times the original value. Therefore, we have $P(\mathcal{I}') = 4P(\mathcal{I})$

Claim: There exists a feasible solution for $\mathcal{I}$ iff there exists a feasible solution for $\mathcal{I}'$.

Proof: $(\to)$ Let $\{x_{i_1},\dotsc,x_{i_{n}}\}$ be a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$. Then, the same solution is a feasible solution of $\mathcal{I}'$ with profit at least $4P(\mathcal{I})/2 \geq 4P(\mathcal{I})/2 - 1 = P(\mathcal{I}')/2 - 1$.

$(\gets)$ Let $\{x_{i_1},\dotsc,x_{i_{n}}\}$ be a feasible solution of $\mathcal{I}'$ with profit at least $P(\mathcal{I}')/2-1 =2P(\mathcal{I}) - 1$. Since the profit values are all even integers, the cost of the solution must be at least $2P(\mathcal{I})$. Then, the same solution is a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$.


This proves that the problem with profit requirement at least $P/2-1$ is $\mathsf{NP}$-hard as well.

$\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.