
University of Bonn > Department of Computer Science > Chair V  
CSReports 1997  Copyright 1997 University of Bonn, Department of Computer Science, 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 