How to Approximate the Bandwidth of a Graph Using Semidefinite Programming?
                      Janez Povh
           School of Business and Management
                  Novo Mesto, Slovenia

                     Franz Rendl
               Department of Mathematik
          University of Klagenfurt, Austria



The Bandwidth problem is an optimization problem where one looks for 
such a labelling of vertices of a graph with distinct integers  which minimizes
the maximum difference between labels on
adjacent vertices.
To find the optimal labelling is proven to be a NP-hard problem.

In this talk we present the heuristics for solving  
semidefinite relaxation
of the Bandwidth problem,
which relies on the interior point methods and on the bundle method.
We  also show  how to transform the proposed randomized algorithm into
deterministic one for some specific classes of graphs (e.g. caterpillars).
The numerical results show the efficiency of the approach.