# Tag Info

## Hot answers tagged approximation-algorithms

7

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

2

I strongly suspect that this is NP-complete, but the approach I have in mind does not seem to work! I wanted to use the the well-known fact that it is NP-complete to decide whether the chromatic index $\chi'(G)$ of a (simple) cubic graph $G$ is $3$ or $4$ (see this paper of Holyer). For the reduction, start with a simple cubic graph $G$ and double each edge ...

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