ECCC-Report TR98-014https://eccc.weizmann.ac.il/report/1998/014Comments and Revisions published for TR98-014en-usFri, 06 Mar 1998 12:38:54 +0200
Paper TR98-014
| On Approximation Intractability of the Bandwidth Problem |
Gunter Blache,
Marek Karpinski,
Juergen Wirtgen
https://eccc.weizmann.ac.il/report/1998/014The 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$.
Fri, 06 Mar 1998 12:38:54 +0200https://eccc.weizmann.ac.il/report/1998/014