1
$\begingroup$

Suppose we have an optimization problem $\mathcal{P}$ that we should cover all points with $k$ disjoint rectangles in the plane and we should optimize a distance function over each rectangles . Now, suppose there is a $\mathcal{P}'$ that just need cover all points in the plane with $k$ disjoint rectangles.

Already proved that $\mathcal{P}'$ is NP-Hard and there is no constant factor approximation algorithm for $\mathcal{P}'$. Can we conclude that $\mathcal{P}$ has no constant factor approximation algorithm? Why?

I think as follow:

$\mathcal{P}$ is at least hard as $\mathcal{P}'$ so if there is a constant factor approximation algorithm for $\mathcal{P}$ then for each feasible solution $\mathcal{I}$ of $\mathcal{P}$, then $\mathcal{I}$ is a solution for decision version of $\mathcal{P}'$ hence we solve decision version of $\mathcal{P}'$ in polynomial time and hence $P=NP$. Finally, we conclude that $\mathcal{P}$ has no constant factor approximation algorithm.

$\endgroup$

1 Answer 1

0
$\begingroup$

Here is a similar example. Let $\mathcal{Q}$ be the problem of maximizing the number of satisfied clauses in an input CNF given that the assignment is the FALSE assignment. Let $\mathcal{Q'}$ be the problem of maximizing the number of satisfied clauses in an input CNF, without any other constraints. It is known that $\mathcal{Q'}$ has no PTAS (unless P=NP). Does it follow that $\mathcal{Q}$ has no PTAS?

$\endgroup$
3
  • $\begingroup$ I think the answer is yes, because $\mathcal{Q}$ at least hard as $\mathcal{Q}'$ so we have no PTAS for $\mathcal{Q}$ (unless P=NP). Can we say my argument is true? $\endgroup$
    – Er7
    Mar 26 at 8:09
  • $\begingroup$ The problem $\mathcal Q$ is actually quite easy. $\endgroup$ Mar 26 at 9:09
  • 1
    $\begingroup$ As my example illustrates, this deduction is invalid. If you’re not sure whether something can be deduced, try working out the deduction from first principles. In other words, convert your intuition into a mathematical proof. $\endgroup$ Mar 26 at 10:43

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.