Friday, April 27, 2012

OSAP - Optimal Seating Arrangement Problem

Recently, I went with bunch of folks from my lab to Ormsby's. We were seated in a pretty big table(rectangular) that could host 16 people, we were 12. Each one of us sat arbitrarily(of course fighting for places with eye catching views(girls!)). We started chatting. I talked for a while with people sitting beside me. Then, I tried to talk to people on the opposite side and other folks. There was so much noise that it was very difficult to have any conversation. After shouting at the top of my voice for a while I got tired and just enjoyed my dinner. For the rest of the time I was thinking of this problem and tried to formalize it in my mind. I tried searching for the problem on Google but could not find anything. So, I named it Optimal Seating Arrangement Problem(OSAP). Below I provide the formal description. Anyone wants to propose an algorithm?

OSAP -  Optimal Seating Arrangement Problem

Problem Statement: Design an algorithm to find an optimal seating arrangement for a group of friends of size n on a round table. Each person in the group has a preference for every other person. The preference values lie between 0 and 1. Also, the sum of the preference values for a person's friends should equal to 1. The optimal arrangement is the arrangement with the highest score where the score of an arrangement is calculated by adding the score of individual person and the score of an individual person is sum of the preference values of his neighbors. A neighbor of a person is someone sitting either to the immediate left or immediate right of the person.

Input: n followed by n X n matrix. Row i contains the preference values of person i for every other person in the group.

Example Inputs:
Input: 3
0 0.1 0.9
0.5 0 0.5
0.6 0.4 0

Output:
1 2 3 or 2 3 1 or 3 2 1or 1 3 2 or 2 1 3 or 3 1 2 ( All of them will have equal score in case of n = 3 )

Input: 4
0 0 0.1 0.9
0 0 0.1 0.9
0.5 0.5 0 0
0.9 0.1 0 0

Output:

3 1 4 2 or any permutation ( 1 4 2 3, 4 2 3 1, 2 3 1 4 )

What is the complexity of the optimal algorithm?