Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1997 Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V 85182 On Approximation Intractability of the Bandwidth Problem Gunter Blache, Marek Karpinski, Juergen Wirtgen [Download PostScript] [Download PDF] The {\em 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 {\em minimal}. The problem has a long history and a number of applications. There was not much known though on approximation hardness of this problem, till recently. Karpinski and Wirtgen \cite{KaWi97b} showed 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 trees. More precisely we show 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.332$. Last Change: 11/05/14 at 10:02:52  English Universität Bonn -> Institut für Informatik -> Abteilung V