2

One way to show that there is no polynomial time approximation algorithm with ratio $c$ for a certain problem X (assuming P≠NP) is to give a reduction $f$ from an NP-hard problem Y to X such that: If $x$ is a Yes instance then the optimal value for X is at least $\beta(x)$, where $\beta(x)$ can be computed from $x$ in polynomial time. If $x$ is a No ...


2

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP). Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the ...


1

No. Since you are performing a many-one reduction, you have no capabilities beyond the model you are using for the reduction, in this case a poly-time Turing machine. Queries to the problem you are reducing to are only allowed if you are performing a Turing reduction, but that is a different notion and (strictly) more powerful than a many-one reduction (and ...


Only top voted, non community-wiki answers of a minimum length are eligible