Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-041 | 18th September 1997 00:00

On Approximation Hardness of the Bandwidth Problem



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