vkgainz's blog

Resources for Balanced Max Cut
By vkgainz, history, 2 years ago, In English

Hello everyone!

I was wondering if anyone had any pointers or useful papers/resources/etc. for a problem I came across today. I tried googling about it for a while but couldn't find anything of much substance, so I decided to take it here. It's called the balanced max cut problem.

A rough description of the problem: You're given an undirected weighted graph $$$G = (V, E)$$$. You want to partition the vertices into $$$k$$$ disjoint components such that each component contains around $$$\frac{n}{k}$$$ vertices (let's say no component can contain more than $$$\epsilon \frac{n}{k}$$$ vertices for some specified $$$\epsilon \geq 1$$$). Find an (approximate) optimal partition such that the sum of edge weights between vertices in different components is maximized.

There are a fair amount of resources that give approximate algorithms solve the balanced min cut problem, which is the same problem as above except the objective is to minimize the sum of edge weights between vertices in different components, instead of maximizing it. However, I don't think they extend very well to the opposite version of the problem. If anyone has any thoughts or resources please do comment! And let me know if I should clarify the problem statement a bit more.

  • Vote: I like it
  • +47
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I found this paper, which could be relevant.

Random thoughts:

  • Intuitively, the max cuts are mostly just balanced.
  • The $$$0.5$$$-approx coin flipping algorithm for Max Cut will also give a balanced cut.
  • Consider the SDP relaxation to Max Cut which is likely optimal. Can you just do some Lagrangian (Aliens trick) sort of thing, like max $$$\frac{1}{2} \sum_{(i, j) \in E}w_{i, j} (1 - x_i x_j) + \sum_{i, j \in V}\lambda (1 - x_i x_j)$$$ for some $$$\lambda > 0$$$ ?
→ Reply