Given a bipartite graph G = (V_1,V_2,E) where edges take on both positive and negative weights from set S, the maximum weighted edge biclique problem, or S-MWEB for short, asks to find a bipartite subgraph whose sum of edge weights is maximized. This problem has various applications in bioinformatics, machine learning and databases and its (in)approximability remains open. In this paper, we show that for a wide range of choices of S, specifically when |min S/max S| ∈ Ω(η~(δ-1/2)) ∩ O(η~(1/2-δ)) (where η = max{|V_1|, |V_2|}, and δ ∈ (0,1/2]), no polynomial time algorithm can approximate S-MWEB within a factor of n~∈ for some ∈ ＞ 0 unless RP = NP. This hardness result gives justification of the heuristic approaches adopted for various applied problems in the aforementioned areas, and indicates that good approximation algorithms are unlikely to exist. Specifically, we give two applications by showing that: 1) finding statistically significant biclusters in the SAMBA model, proposed in [18] for the analysis of microarray data, is n~∈-inapproximable; and 2) no polynomial time algorithm exists for the Minimum Description Length with Holes problem [4] unless RP = NP.
展开▼
机译：给定二部图G =（V_1，V_2，E），其中边集S上的边同时承担正和负权重，则最大加权边二等问题（简称S-MWEB）要求找到其边和之和的二部子图权重最大化。这个问题在生物信息学，机器学习和数据库中有各种应用，其（in）近似性仍然存在。在本文中，我们证明了对于广泛的S选择，特别是当| min S / max S | ∈Ω（η〜（δ-1/ 2））∩O（η〜（1 /2-δ））（其中η= max {| V_1 |，| V_2 |}，δ∈（0,1 / 2 ]），除非RP = NP，否则对于某些ε＞ 0，没有多项式时间算法可以在n〜∈的因子内近似S-MWEB，这一硬度结果证明了在上述领域中针对各种应用问题所采用的启发式方法的合理性，并指出具体来说，我们通过以下两个例子给出两个应用：1）在[18]中提出的用于分析微阵列数据的SAMBA模型中，发现具有统计显着性的二聚体是n〜ε不可近似的； 2）除非RP = NP，否则不存在带孔的最小描述长度问题[4]的多项式时间算法。
展开▼
