Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, B_2)$ is maximum, where $w(A_i, B_i) := \sum\limits_{\{a,b\}\in (A\times B)\cap E}w(a,b)$.

I think this problem is already known but I couldn't find any reference. Does anyone know any related problems? Or is this problem NP-hard?

  • $\begingroup$ Surely to maximize the sum, you should let $A_1$ and $B_1$ be as big as possible; and $A_2$ and$B_2$ as small as possible (ideally empty). The harder problem would be to minimize the sum (or maybe you constrain the size of the $A$’s and $B$’s. Also this is not really a problem about graphs. You could ask the same problem just about matrices with non-negative entries. $\endgroup$ – Anthony Quas Jun 17 '18 at 20:06
  • $\begingroup$ Thanks for your comment. But I don't think so. The minimization problem is equivalent to the maximization one because the weight $w$ can be positive or negative. $\endgroup$ – Thomas Edison Jun 18 '18 at 8:19
  • $\begingroup$ If that’s what you have in mind, you should say so explicitly in the question as in this kind of area, weights are generally assumed to be positive. $\endgroup$ – Anthony Quas Jun 18 '18 at 15:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.