1

I have a large wedding of 500 people and 100 tables, each table containing 5 seats. Each person at the wedding lists (up to) 4 people they would like to sit at their table (order of the ranking matters). The more people they sit with, the happier they are.

What is best way of finding the optimal solution that the most people are happy?

I am considering linear programming, specifically max flow min cut, but I'm unsure of how to map the constraints/problem.

afathman
  • 111
  • It sounds like you'd need to establish some sort of happiness point system, where a person getting a particular list item adds a certain number of points. I can't really answer your question, but I can tell you two things. First, a brute force approach has exponential time complexity. Second, even finding the largest group of people that want to sit next to each other looks NP hard, so not likely to be a lot better than exponential. That is quite a different problem, but it seems simpler than what you are asking. I bet you've got an NP hard problem here, which is impractical for 500 guests. – jack May 09 '15 at 04:33

1 Answers1

1

This blog post demonstrates one approach that uses mixed integer linear programming: https://blogs.sas.com/content/operations/2014/11/10/do-you-have-an-uncle-louie-optimal-wedding-seat-assignments/

RobPratt
  • 45,619