Hot answers tagged

12

The answer for (1) is "unlikely". It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$. That said, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard. As for (2), perhaps you could phrase it as "Does not ...


7

Suppose you have a reduction $f$ from problem $A$ to problem $B$. So if $f(x) \in B$ then $x \in A$ and if $f(x) \notin B$ then $x \notin A$ (here $x \in A$ means $x$ is a YES instance of $A$). Now suppose that $A$ and $B$ are in fact optimization problems, say both are maximization problems. Now $f$ maps an instance $(x,a)$ of $A$ to an instance $(y,b)$ of ...


4

If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta >0$ runs in polynomial time and approximates the problem within a factor of $1+\epsilon$ with probability $1-\delta$, then $\mathsf{NP} \subseteq \mathsf{BPP}$. The reasoning is very similar to Chandra's answer to another question. APX-hardness for a problem $P$...


1

This is perhaps not entirely satisfactory since you asked for an approximation rather than a hardness result but there is no constant independent of $a$ for which the problem can be approximated to within via an FGLSS-like reduction. Unless P=NP, for every $\epsilon > 0$, there exists $c_0$ such that there is no poly-time $\epsilon$-approximation for ...


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