Seating arrangement problem

Question

$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$

Each professor has people they like to sit next to and people they do not want to sit next to. Given a $n\times n$ (non-symmetrical) matrix $M$ where $M_{ij}$ gives the score assigned by professor $i$ if s/he is made to sit next to professor $j$ and $M_{ii}=0$, the goal is to output a symmetrical indicator matrix $I$ where $I_{ij} = 1$ if professor $i$ is sitting next to professor $j$ such that $\sum M.*I$ is maximized (I used Matlab notation here to denote elementwise multiplication of two matrices). How can we find this optimal arrangement? Lets assume we are dealing with even $n$.

From my side I spent some time calculating the total # of possible arrangements for given $n$ and arrived at this formula: $\frac{C^n_{n/2}}{2}(\frac{(n/2)!}{k})^2$ where $k = 1$ if $n = 2$ and $k = 2$ otherwise.

I wrote the following program to calculate the # of different arrangements for given value of $n$ (assume even $n$) according to above formula.

public static void main(String[] args) {
        for(int i = 2; i <= 10; i += 2)
        {
            System.out.printf("%d\t%s\n", i, foo(i).toString());
        }
    }

    static BigInteger foo(int n)
    {
        BigInteger t1 = binomial(n, n/2).divide(BigInteger.valueOf(2));
        BigInteger t2 = factorial(n / 2);
        BigInteger t3 = n >= 4 ? BigInteger.valueOf(4) : BigInteger.ONE;
        return t1.multiply(t2).multiply(t2).divide(t3);
    }

    // http://stackoverflow.com/a/2929897/147530
    static BigInteger binomial(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N-k))
                    .divide(BigInteger.valueOf(k + 1));
        }
        return ret;
    }

    static BigInteger factorial(int n) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 2; k <= n; k++) {
            ret = ret.multiply(BigInteger.valueOf(k));
        }
        return ret;
    }

Output:

2   1
4   3
6   90
8   5040
10  453600

Answer 1

Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(.

NP-Hardness

Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or above some $k$?

This problem is NP-Complete.

First, clearly this decision problem is in NP, as if one can provide you with such an assignment then you can compute the total score and verify that their solution works.

Next, note that this problem is essentially equivalent to finding two distinct highest-cost paths that go through the same amount of nodes, and together go through every node. Using this idea, we will solve the hamiltonian path problem.

Given two hamiltonian path instances $G_1=(V_1, E_1)$ $G_2=(V_2, E_2)$ of the same size $n$, consider the combined graph $G=(V_1\cup V_2, E_1 \cup E_2)$, and then create an instance of our seating arrangement problem where every edge is a $1$ if it occurs in our combined graph, and a $0$ otherwise. Because these graphs are undirected, the preferences will be the same in both directions.

The question "is there some way to assign seating positions to professors such that the total score obtained is greater than or equal to $\vert V_1 \vert + \vert V_2 \vert$" is NP-Complete, as it is only possible to do this if a hamiltonian path exists in both graphs.

Approximation algorithm ideas

NP-Hardness just guarantees that a problem can't always be solved exactly unless $P=NP$, however, it doesn't tell us anything about how difficult it is to approximate. Here is one idea I had, it's incomplete, but is at least something to get you started.

For simplicity, I will now consider the problem where there is a single circle of chairs, and we are trying to place professors in the same way you require. We will also restrict all preferences to be greater than or equal to 0. This can most likely be extended to your problem but I haven't got around to that yet, so I will update this problem once that is accomplished, or you can do this yourself.

With this "roundtable" problem, it turns out there is an algorithm I found that is guaranteed to find a solution that is no less than 8 times the optimal solution.

This algorithm does the following:

1. Place each person randomly around the table.
2. Consider a pair of people (any will do), and see if swapping them will increase the total score. If so, swap them.
3. Repeat until no swap will increase your total score.

This is guaranteed to halt in polynomial time because each swap strictly increases the total score (I think? Still a little fuzzy about this part but I'm fairly sure that is true and will formalize it in a bit).

How good does this algorithm do? Well, call $Opt$ the optimal ordering of professors, and $Val$ the ordering of professors that this algorithm gives when it is done.

Now, consider any set of edges $(a, x)$, $(x, b)$, $(c, y)$, $(y, d)$ in your graph, where $a, x, b, c, y, d$ are professors. We will denote these edges $(a,x,b)$ and $(c, y, d)$ since by definition given any arrangement of professors they are next to each other.

We know that, if $y$ and $x$ could be swapped our algorithm would have done so. Call $\mid (a, x, b)\mid$ the score of edge $(a, x)$ plus the score of edge $(x, b)$. Then, if $(a, y, b)$ and $(c, x, d)$ are in val, we know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)|$$

Because either our algorithm swapped $x$ with $y$, or there was equal score regardless of the swap, in which case we have

$$|(a, y, b)| + |(c, x, d)| = |(a, x, b)| + |(c, y, d)|$$

Note that we technically also know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)| \geq |(c, y)|$$

Which is true because $|(a, x, b)| + |(c, y, d)|$ contains $|(c, y)|$ in it. Now we can look at the terms on both ends, and this gives us

$$|(a, y, b)| + |(c, x, d)| \geq |(c, y)|$$

Which holds for all edges $(c, y)$. Note that given any $(c, y)$, there is only one such pair of $(a, y, b)$ and $(c, x, d)$, because the positions $c$ and $y$ are fixed.

We know that the value of $Opt$ is equal to the sum of all it's edges $(v_1, v_2)$, $(v_2, v_3)$, ..., $(v_{n-1}, v_n)$, $v_n, v_1)$ (where $v_i$ is some professor), so for each of these, we get a single inequality. Consider the edge $(a, y)$. $|(a, y)|$ will only appear in an inequality if $a$, $y$, or the professor before $a$ is contained in the edge in Opt. Thus, worst case $(a, y)$ is counted 8 times, because each variable can be in at most two edges, by definition.

If we sum all of the edges on both sides, we get

$$8*Val\geq Opt$$

Thus

$$(8 \geq \frac{Opt}{Val})$$

which is a factor 8 approximation, as desired.

Answer 2

Super late to this party, but Phylliida is correct. This is an NP-hard problem so there is no "efficient" solution, and the proposal is known as "simulated annealing" which is the best you are going to get.

Look up wedding seating for a bunch of articles on why it is NP complete.

-- Henry

Answer 3

If the table is round, then this problem is a variant of the famous Travelling Salesman Problem and any of the many solutions in published literature can be consulted for solving it.