The bandwidth problem is the problem of numbering the vertices of a
given graph $G$ such that the maximum difference between the numbers
of adjacent vertices is minimal. The problem has a long history and
is known to be NP-complete Papadimitriou [Pa76]. Only few special
cases of this problem are known to be efficiently approximable. In
this paper we present the first constant approximation ratio
algorithms on dense instances of this problem.