
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 1997  Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V  
8943

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 