  Given a graph $G=(V, E)$ and and a proper labeling $f$ from $V$ to $\{1, ...,
n\}$, we define $B(f)$ as the maximum absolute difference between $f(u)$ and
$f(v)$ where $(u,v)\in E$. The bandwidth of $G$ is the minimum $B(f)$ for all
$f$. Say $G$ is $\delta$-dense if its minimum degree is $\delta n$. In this
paper, we investigate the trade-off between the approximation ratio and the
time complexity of the classical approach of Karpinski {et al}.\cite{Karpin97},
and present a faster randomized algorithm for approximating the bandwidth of
$\delta$-dense graphs. In particular, by removing the polylog factor of the
time complexity required to enumerate all possible placements for balls to
bins, we reduce the time complexity from $O(n^6\cdot (\log n)^{O(1)})$ to
$O(n^{4+o(1)})$. In advance, we reformulate the perfect matching phase of the
algorithm with a maximum flow problem of smaller size and reduce the time
complexity to $O(n^2\log\log n)$. We also extend the graph classes could be
applied by the original approach: we show that the algorithm remains polynomial
time as long as $\delta$ is $O({(\log\log n)}^2 / {\log n})$.
