6
$\begingroup$

I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:

  • There is a value $\epsilon_1$ such that approximation within a factor of $\epsilon_1$ is possible in polynomial time.
  • There is a value $\epsilon_2$ such that approximation within a factor of $\epsilon_2$ is NP-hard.
  • There is some value $\epsilon$ between $\epsilon_1$ and $\epsilon_2$ such that approximation within a factor of $\epsilon$ are neither in polynomial time nor NP-Hard.

(There is a general question about NP-intermediate problems here, but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)

$\endgroup$
2
$\begingroup$

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.

$\endgroup$

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.