English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Given a bipartite graph G = (V1, V2, 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{|V1|, |V2|}, 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.

Inapproximability of Maximum Weighted Edge Biclique and Its Applications