For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar towards each other.

I'm trying to find a subset of size $k$ nodes such that they look not so "similar" towards one another, $\textrm{i.e.}$ $k$ nodes $G_k = (V_k, E_k)$ s.t. $\sum_{(i,j) \in E_k} w_{ij}$ is maximized.

I'm not looking for an exact solution but I do want to know whether there is an approximation algorithm that is easy to implement and can still have some kind of performance guarantee.

  • 1
    $\begingroup$ Do you really want an approximation algorithm that is NOT easy to implement? $\endgroup$ – Yoshio Okamoto Mar 2 '13 at 4:07
  • $\begingroup$ Negative of the function you are trying to maximize can be shown to be a submodular function on the set of nodes. So your problem can be stated as a submodular minimization problem, which has been well studied. There must be some approximation algorithms for minimizing over subsets of fixed size $k$. $\endgroup$ – polkjh Mar 2 '13 at 5:57
  • $\begingroup$ @YoshioOkamoto: Oops...should be "easy to implement". :) $\endgroup$ – derekhh Mar 2 '13 at 6:11
  • 1
    $\begingroup$ The submodular function we get in your case is even more special, it is an increasing function. It might be possible to use that too. But these are some papers on minimizing general submodular functions with constraints on size of subsets. algorithmofsaintqdd.googlecode.com/svn/trunk/Papers/ML/ICML2011/… and arxiv.org/pdf/0805.1071v3.pdf $\endgroup$ – polkjh Mar 2 '13 at 7:13
  • 2
    $\begingroup$ In fact, it seems your problem is a standard one, called densest $k$-subgraph problem. citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$ – polkjh Mar 2 '13 at 7:21

Your Answer

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

Browse other questions tagged or ask your own question.