TR97-041 Authors: Marek Karpinski, Juergen Wirtgen

Publication: 19th September 1997 14:56

Downloads: 1975

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

and is known to be $NP$-hard, Papadimitriou 1976.

There is not much known though on approximation hardness

of this problem. In this paper we show, that there are no

efficient polynomial time approximation schemes for the

bandwidth problem under some plausible assumptions.

Furthermore we show that there are no polynomial time

approximation algorithms with an absolute

error guarantee of $n^{1-\epsilon}$ for any

$\epsilon >0$ unless $P=NP$.