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)$:
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?
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$.
External links referenced by this document: