Hardness of approximation of the Balanced Complete Bipartite Subgraph problem
Hardness of approximation of the Balanced Complete Bipartite Subgraph problem
复制标题
平衡完全二分子图问题的逼近难度
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Shimon Kogan
中科院分区：
文献类型：
--
作者：
U. Feige;Shimon Kogan
证明了在3-SAT ∈ DTIME（2 3/4+）的合理假设下，对于δ > 0，极大平衡完全二部子图（BCBS）问题很难在因子2（n）δ内逼近.我们还表明，它是NP -难近似的BCBS问题在一个常数因子的假设下，它是NP -难近似的最大团问题在一个因子n/2 lg n的一些足够小的c > 0。此外，我们表明，同样的硬度的近似结果持有的最大边Biclique问题。
We prove that the Maximum Balanced Complete Bipartite Subgraph (BCBS) problem is hard to approximate within a factor of 2 n) δ for some δ > 0 under the plausible assumption that 3-SAT ∈ DTIME ( 2 3/4+ ) for some > 0. We also show that it is NP -hard to approximate the BCBS problem within a constant factor under the assumption that it is NP -hard to approximate the maximum clique problem within a factor of n/2 √ lg n for some small enough c > 0. Furthermore we show that the same hardness of approximation results holds for the Maximum Edge Biclique problem.