Happy Triplets

Правка en1, от RodionGork, 2023-03-07 08:41:56

three men inventing something to drink

We know the problem of "maximal pair matching" (or "maximal matching in bipartite graph) — one of solutions for it is via "maximum flow" algorithms.

But how to solve certain extension of the problem?

Statement

There is a set of 3*N persons, gender-agnostic. We want to split them into N groups of 3.

For every two of them we know the value of mutual happiness of being together in the same group (e.g. we have a diagonally symmetric table 3N by 3N of happiness).

Now, how to maximize happiness? Assuming happiness of a group is sum of 3 pair's happiness in it — and total happiness is the sum over group's happiness.

Any ideas? Iterative random swaps may help in improving happiness but is there precise solution (without brute-force iterating over all possible group arrangements as their number increases pretty fast).

Thanks in advance!

Теги algorithms, question, graphs, combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский RodionGork 2023-03-07 08:41:56 980 Initial revision (published)