ECCC-Report TR97-041https://eccc.weizmann.ac.il/report/1997/041Comments and Revisions published for TR97-041en-usFri, 19 Sep 1997 14:56:52 +0200
Paper TR97-041
| On Approximation Hardness of the Bandwidth Problem |
Marek Karpinski,
Juergen Wirtgen
https://eccc.weizmann.ac.il/report/1997/041The 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$.
Fri, 19 Sep 1997 14:56:52 +0200https://eccc.weizmann.ac.il/report/1997/041