# 二叉樹上最小帶寬的近似值

## 最佳答案

Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no PTAS for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an approximation factor of $k$. So, unfortunately there's no PTAS nor APX for the problem.

Cygan M.和Pilipczuk M 。，甚至更快的精確帶寬，2012 。該算法以$O（4.83 ^ n）$ time運行。