tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a group.

I have a directed graph with edge weights $w_{uv}$ between vertices $u$ and $v$ that can be both negative and positive. Edges not present in the graph can be considered to have $w_{uv}=0$.

My goal is to partition the vertices into mutually disjoint subsets $s_1,s_2,\ldots,s_k$ such that $4\leq |s_i|\leq 5$, i.e. the subset sizes are either four or five, the subsets do not all need to be of the same size.

I want the partition that maximizes $\sum_{i=1}^k\sum_{i,j\in S_i} w_{ij}$ (that is, I want to maximize happiness in some sense).

Is there an algorithm that solves this in polynomial time? If not, what if the maximum degree of every vertex is bounded by some constant?

I thought of framing it as an integer optimization problem as follows:

The variables are given by $c_{u,v,i}$ ($u\leq v$) and we have $c_{u,v,i} = 1$ if and only if vertices $u$ and $v$ are both assigned to subset $s_i$.

I then want to maximize $$\sum_{i=1}^k\sum_{1\leq u<v\leq n} (w_{uv}+w_{vu})c_{u,v,i}.$$

Subject to the following constraints:

For each vertex $u$ we need to have

$$\sum_{i=1}^k c_{u,u,i}=1$$

to guarantee that the vertex can only be in one subset.

For each vertex $v$ and each subset $i$ we need

$$\sum_{u=1, u\neq v}^n c_{u,v,i}\leq 5\cdot c_{v,v,i}$$

to guarantee that we only have positive values for $v$ in a single subset and to upper bound the number of other vertices in that subset.

We then add similarly

$$\sum_{u=1, u\neq v}^n c_{u,v,i}\geq 4\cdot c_{v,v,i}$$

to guarantee a lower bound on the subset sizes.

I think I'm not missing anything in this framing but I am wondering for what size of graphs this is a feasible approach and whether I'm missing a simpler approach. I have a greedy approximation approach but I'm curious what else can be done as I did not find many references online (most likely I did not look for the right keywords).

  • 1
    $\begingroup$ Look for 3-D matching. $\endgroup$ – Chandra Chekuri Jan 20 at 2:36

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.