Computer Science – Computational Complexity
Scientific paper
2007-04-03
LNCS 4978, TAMC 2008, pp 282-293
Computer Science
Computational Complexity
Scientific paper
Given a bipartite graph $G = (V_1,V_2,E)$ where edges take on {\it both} positive and negative weights from set $\mathcal{S}$, the {\it maximum weighted edge biclique} problem, or $\mathcal{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 $\mathcal{S}$, specifically when $| \frac{\min\mathcal{S}} {\max \mathcal{S}} | \in \Omega(\eta^{\delta-1/2}) \cap O(\eta^{1/2-\delta})$ (where $\eta = \max\{|V_1|, |V_2|\}$, and $\delta \in (0,1/2]$), no polynomial time algorithm can approximate $\mathcal{S}$-MWEB within a factor of $n^{\epsilon}$ for some $\epsilon > 0$ unless $\mathsf{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 \cite{Tan02} for the analysis of microarray data, is $n^{\epsilon}$-inapproximable; and 2) no polynomial time algorithm exists for the Minimum Description Length with Holes problem \cite{Bu05} unless $\mathsf{RP=NP}$.
No associations
LandOfFree
Inapproximability of Maximum Weighted Edge Biclique and Its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Inapproximability of Maximum Weighted Edge Biclique and Its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of Maximum Weighted Edge Biclique and Its Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-213235