Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-041 | 18th September 1997 00:00

#### On Approximation Hardness of the Bandwidth Problem

TR97-041
Authors: Marek Karpinski, Juergen Wirtgen
Publication: 19th September 1997 14:56
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
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$.

ISSN 1433-8092 | Imprint