Publication Details
Title: On Approximation Hardness of the Bandwidth Problem
Author: M. Karpinski and J. Wirtgen
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-060.pdf
Overview:
The 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 minimal. The problem has a long history and a number of applications and is known to be NP-hard, Papadimitriou [Pa 76]. 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-e for any e > 0 unless P = NP.
Bibliographic Information:
ICSI Technical Report TR-97-060
Bibliographic Reference:
M. Karpinski and J. Wirtgen. On Approximation Hardness of the Bandwidth Problem. ICSI Technical Report TR-97-060, December 1997
Author: M. Karpinski and J. Wirtgen
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-060.pdf
Overview:
The 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 minimal. The problem has a long history and a number of applications and is known to be NP-hard, Papadimitriou [Pa 76]. 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-e for any e > 0 unless P = NP.
Bibliographic Information:
ICSI Technical Report TR-97-060
Bibliographic Reference:
M. Karpinski and J. Wirtgen. On Approximation Hardness of the Bandwidth Problem. ICSI Technical Report TR-97-060, December 1997