TR98-014 Authors: Gunter Blache, Marek Karpinski, Juergen Wirtgen

Publication: 6th March 1998 12:38

Downloads: 1507

Keywords:

The bandwidth problem is the problem of enumerating

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 a number of applications.

There was not much known about approximation hardness

of this problem till recently.

Karpinski and Wirtgen proved recently that there are no polynomial

time approximation algorithms with an absolute error guarantee

of $n^{1-\epsilon}$ for any $\epsilon >0$ unless $P=NP$.

In this paper we show, that there is no $PTAS$ for the bandwidth

problem unless $P=NP$, even for the trees. More precisely we prove

that there are no polynomial time approximation algorithms

for general graphs with an approximation ratio better than $1.5$,

and for the trees with an approximation ratio better than

$4/3 \approx 1.333$.