Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-014 | 6th February 1998 00:00

#### On Approximation Intractability of the Bandwidth Problem

TR98-014
Authors: Gunter Blache, Marek Karpinski, Juergen Wirtgen
Publication: 6th March 1998 12:38
Keywords:

Abstract:

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$.

ISSN 1433-8092 | Imprint