On Approximation Intractability of the Bandwidth Problem
On Approximation Intractability of the Bandwidth Problem
复制标题
带宽问题的近似难解性
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
J. Wirtgen
中科院分区：
文献类型：
--
作者：
Gunter Blache;Marek Karpinski;J. Wirtgen
{em 带宽问题} 是枚举给定图 $G$ 的顶点，使得相邻顶点数量之间的最大差为 {em 最小} 的问题。该问题有着悠久的历史和广泛的应用。直到最近，人们对这个问题的近似硬度还知之甚少。 Karpinski 和 Wirtgen 引用{KaWi97b} 表明，对于任何 $epsilon <0$，不存在绝对误差保证为 $n^{1-epsilon}$ 的多项式时间逼近算法，除非 $P=NP$。在本文中，我们表明，除非 $P=NP$，否则带宽问题不存在 $PTAS$，即使对于树也是如此。更准确地说，我们表明，对于近似率优于 $1.25$ 的一般图，以及对于近似率优于 $7/6 的树（约 1.167$），不存在多项式时间近似算法。
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.25$ and for trees with an approximation ratio better than $7/6 approx 1.167$.