Resources for Balanced Max Cut

Revision en1, by vkgainz, 2022-11-23 12:15:24

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.


  Rev. Lang. By When Δ Comment
en1 English vkgainz 2022-11-23 12:15:24 1273 Initial revision (published)