Approximation of minimum bandwidth on binary trees

Question

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes.

The decision problem is NP-complete even for binary trees. Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978.

What is the best known efficient approximability result for computing minimum bandwidth on binary trees? What is best known conditional hardness of approximation result?

Answer 1

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.

However, for some types of graphs, the problem can be solved or approximated in polynomial time. For a recent survey, see Petit J., Addenda to the Survey of Layout Problems, 2011. In the survey, see Tables 3, 4 and 8. The survey also gives a nice list of references if you want to dig in deeper to some direction. This is an more updated version of the older survey by Diaz et al., A survey of Graph Layout Problems, 2002.

In case you are interested in the exact algorithm as well, I think currently the fastest one is given by Cygan M. and Pilipczuk M., Even Faster Exact Bandwidth, 2012. The algorithm runs in $O(4.83^n)$ time.