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
85178

On Approximation Hardness of the Bandwidth Problem
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 and is known to be $NP$-hard, Papadimitriou \cite{Pap76}. There is not much known though on approximation hardness of this problem. In this paper we show, that there are no efficient polynomial time approximation schemes for the bandwidth problem under some plausible assumptions. Furthermore we show that there are no polynomial time approximation algorithms with an absolute error guarantee of $n^{1-\epsilon}$ for any $\epsilon >0$ unless $P=NP$.

Last Change: 11/05/14 at 10:05:08
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope