#StackBounty: #code-challenge #fastest-algorithm Meeting splitter

Bounty: 50

Introduction

Large meetings waste working time. Our aim is to split a large meeting into a number of smaller meetings, so the average number topics that a person discusses is minimized but every person has to be in every meeting they are interested in.

Input

Given is a function from a set of topics T to a set of persons P that are interested in this topic $$f:T rightarrow 2^P$$ and maximum partition size m.

This is encoded as an array of arrays, where element f[i] contains the topics of person i.

Test Case

m = 3
f = [
[9,7],
[3,7,6,4],
[3,1,2],
[7,5,4,2],
[6,2,8,1,4],
[3,7,2,9,8],
[4,3,2],
[3,4,6],
[1,9,5,3],
[6,4,1,2],
[9,7,3,1],
[1,7,4],
[5,1,7,2],
[5,2,7],
[4,2,6,9],
[6,4,1],
[6,5,9,8],
[9,1],
[9,1,5,6],
[1,2,4,8,7]                                                                     
]

Output

Find a partition of T (a split into subsets that are disjoint and that cover the whole set) into $$X = {T_1, T_2, ldots, T_n}$$ where n<=m, so that the following term is minimized:
$$r = sum_{T’ in X}{(|(bigcup_{t in T’} f(t))|times |T’|)} $$

To help understand r, if each topic takes an hour to discuss, then r is the total amount of person hours required for the meetings.

If there are multiple partition sizes with the same r, n should be minimized as well.

The output should contain the partition X as a two-dimensional array, such as:
$$X = [[0,1,2,3],[4,5,6],[7,8,9]] $$

Winning Condition

I am looking for the fastest algorithm that finds the absolute minimum r and n.

If that is not possible in polynomial time, then I am also looking for an polynomial algorithm that has the lowest upper bound on r in relation to the absolute minimum r (e.g. double).


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.