CODEWITHSUNDEEP
algorithmoptimization
Wolfgang
Wolfgang

Reputation: 21

Optimized distribution of events to dates

My problem is to find the best distribution of a number k of events on 3 evenings. For example k=8 events should be equally distributed on these 3 evenings:

On the other side I have a group of people who have to go to different events like:

The question is: How can I find the best distribution of the events to the evenings so that the number of rides for the people is minimized?

For the example above, I know that there are 560 different possibilities to distribute the 8 events on the 3 evenings. I could brute force them and compare the number of required rides but hoped to find a better alternative.

Upvotes: 2

Views: 52

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

This is equivalent to hypergraph partitioning with the connectivity objective (λ - 1). The nodes of the hypergraph are the events. The hyperedges correspond to the people, with each hyperedge connecting the events that the corresponding person has to attend.

There's a vast literature on hypergraph partitioning and a good number of implementations. I'd start with KaHyPar.

Upvotes: 2

Related Questions