# Inapproximability of an optimization problem

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.

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?
• 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?
• The problem $\mathcal Q$ is actually quite easy. Mar 26 at 9:09