Rheinische Friedrich-Wilhelms-Universität Bonn 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

Powered by Zope