0
$\begingroup$

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\ldots, V_k$ of $V$, i.e, $V_i\cap V_j = \emptyset, \cup_{i=1}^k V_i = V$, the cost $K(U_1,\ldots,U_k,V_1,\ldots,V_k)$ is defined as follows. $$K(U_1,\ldots,U_k,V_1,\ldots,V_k) = \sum\limits_{e\in E(U_i,V_i), i=1,\ldots,k} w(e),$$ where $E(U_i,V_i)$ is the edges set between $U_i$ and $V_i$. My question is to find nonempty sets $U_i$ and $V_i$ as above that maximizes $K(U_1,\ldots,U_k,V_1,\ldots,V_k)$ for a given $k \in \mathbb{N}$.

I have no idea to solve this problem. Does anyone have any idea or know any related problem. Thank you in advance!

$\endgroup$

1 Answer 1

2
$\begingroup$

The case $k=2$ is addressed in the paper https://arxiv.org/abs/cs/0108018 (Bipartite graph partitioning and data clustering by H. Zha, X. He, C. Ding, M. Gu, H. Simon)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy