0
$\begingroup$

I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\epsilon$-multiplicative approximation), in a sense defined as follows:

Formally, let $L\subseteq\Sigma^*\times \mathbb N$ be the decision version of some minimization (or maximization, flipping the definitions) problem, i.e. $$\forall n\leq m:(w,n)\in L\implies (w,m)\in L$$

Which examples of such known languages $L$ is $NP$-hard, but if we are allowed of a minimal relaxation, it is poly time solvable.

By minimal relaxation I mean that there exists a TM such that given an input $(w,n)$:

  • The machine accepts if $(w,n+1)\in L$.
  • The machine rejects if $(w,n-1)\not \in L$.
  • The machine may act arbitrarily on other cases.

An example for such problem is the Degree-constrained spanning tree, where the problem is finding an MST with minimal maximum vertex degree.

Which other languages are NP-hard but subject to optimal approximation in poly time?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 3-coloring problem on planar graphs is $NP$-hard while every planar graph is 4-colorable in polynomial time (by the four color theorem). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 1, 2015 at 15:51
  • $\begingroup$ I guess there is an issue of discretization that is tricky. For example, if we want to formalize Max-Cut in this framework, what is the meaning of $n+1$ and $n-1$? $\endgroup$
    – usul
    Commented Feb 1, 2015 at 16:27
  • 2
    $\begingroup$ Maybe better term for optimal approximation or minimal relaxation is approximation with additive constant error. $\endgroup$
    – Saeed
    Commented Feb 1, 2015 at 18:29
  • 1
    $\begingroup$ @Saeed, can you explain how that's equivalent? I think the issue is that I still don't understand what the role of the constant $1$ is in the definition. $\endgroup$
    – usul
    Commented Feb 2, 2015 at 0:17
  • 1
    $\begingroup$ @usul I didn't understand what you don't understand. But you can search about additive constant error to understand what it is, assuming you know this, OP's question is about additive error 1 (replace constant with 1) $\endgroup$
    – Saeed
    Commented Feb 2, 2015 at 8:05

1 Answer 1

Reset to default
3
$\begingroup$

One example is the chromatic index (edge-coloring number) of undirected graphs. By Vizing's theorem, the chromatic index either equals the max-degree $\Delta$ or equals $\Delta+1$.

  • Vizing's proof gives a polynomial time (inductive) procedure for finding a coloring with $\Delta+1$ colors.
  • Holyer has proved that deciding whether the chromatic index equals $\Delta$ is NP-complete.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.