Computer Science Asked by yuezato on November 11, 2021
I am considering the following maximization problem:
As an example, for the collection
$$
mathcal{F} = { {a, b, c}, {a, b, c, x}, {b, c, y}, {a, b, c, z} },
$$
the maximizing subset is $G = { {a, b, c}, {a, b, c, x}, {a, b, c, z} }$
and the score is $3 times |{a, b, c}| = 9$.
Note: the score of $mathcal{F}$ itself is $4 times |{b, c}| = 8$.
I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets).
However, I don’t have any good idea to solve this problem efficiently.
As yow know, we can solve this by enumerating all the collections of $mathcal{F}$; but, it’s too slow for practical use.
Is there a polynomial-time or some kind of efficient algorithm for this problem?
Or, does this problem belong to the complexity class that cannot be solved in polynomial time?
This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where
Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete", the decision problem is NP-complete.
Answered by user114966 on November 11, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP