4
$\begingroup$

Say we have two (NP-)optimization problems $A$, resp. $B$, such that it is NP-hard to approximate within a factor $\alpha$ resp. $\beta$.

Now define problem $C$ whose input consists of pair inputs from $A$ and $B$, and a solution as pair of solutions of $A$ and $B$, but the objective function as the product of objective functions of $A$ and $B$.

Can we conclude that $C$ is NP-hard to approximate within a factor $\alpha\beta$? If not, can we prove anything stronger than that there is no approximation within $\max\{\alpha, \beta\}$? If yes, does it matter if the hardness depends on, for example, the unique games conjecture?

Intuitively, I would think: unless $P=NP$, for any polytime approximation algorithm for $A$ there is an input such that it gives a solution of cost more than $\alpha OPT$, and likewise for $B$. Any algorithm for $C$ can be used almost directly as an algorithm for either $A$ or $B$, so we can find an input that produces a solution of cost more than $\alpha \beta OPT$ on that algorithm as well. I am not sure if you can reason like this though.

$\endgroup$
  • $\begingroup$ I suspect you might be able to find A, B such that having an instance of B at hand helps in solving A. The B instance can serve as a polynomial advice string. $\endgroup$ – adrianN Jan 26 '17 at 15:45
  • 1
    $\begingroup$ @adrianN, that doesn't sound right to me, as here the language is $\{(a,b) : a \in A, b \in B\}$, so $a,b$ are uncorrelated. $\endgroup$ – D.W. Jan 26 '17 at 17:18
3
$\begingroup$

When we say that a minimization problem A is NP-hard to approximate up to a factor $\alpha \geq 1$, we mean that there is a polynomial time reduction $f$ from instances $\varphi$ of SAT to instances $x$ of A annotated by a target value $\theta$ such that:

  • If $\varphi$ is satisfiable then $A(x) \leq \theta$ (where $A(x)$ is the optimal value of $x$).
  • If $\varphi$ is not satisfiable then $A(x) > \alpha \theta$.

Using this definition it is not hard to prove the multiplicative property.


You can also consider a more general notion of hardness: if there is a polynomial time $\alpha$-approximation algorithm for A, then P=NP. Even under this notion, a $\alpha$-hardness for A translates to a $\alpha^2$-hardness for "A2". Indeed, given an instance of A, duplicate it and pass it to the $\alpha^2$-approximation algorithm. One of the solutions is an $\alpha$-approximation. If only the objective value is given, then the smaller one is an $\alpha$-approximation.

$\endgroup$
  • $\begingroup$ Thanks! Now you've put it like this it seems so simple indeed. Just for clarification, in the second notion of hardness does it still necessarily hold if $A\neq B$? And does it also work if we replace P=NP with a stronger assumption? $\endgroup$ – Thomas Bosman Jan 26 '17 at 18:06
  • $\begingroup$ It works for all reasonable assumptions, but only when A=B. $\endgroup$ – Yuval Filmus Jan 26 '17 at 18:14

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.