Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to

hello@diophantus.org
####
pdf
Inapproximability of Maximum Weighted Edge Biclique and Its Applications

**Abstract**. 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}$.

# Reviews

There are no reviews yet.

# Comments

Log in to leave a comment.

# Reviews

There are no reviews yet.

Log in to leave a review.

There are no comments yet.