1
$\begingroup$

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

enter image description here

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
$\endgroup$
  • $\begingroup$ "non-symmetrical" ​ -> ​ "not-necessarily-symmetric" ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 5 '16 at 22:37
  • $\begingroup$ yes. professor $i$ may like sitting next to professor $j$ but professor $j$ may not want to sit next to professor $i$ $\endgroup$ – morpheus Feb 5 '16 at 23:41
  • 2
    $\begingroup$ Two questions: is the table always two rows of chairs, each of the same length? (Or one more on one side if the total number of professors is odd). Also,what is meant by best arrangement? Maximize total score after seating? Minimize least displeasure? Have a low variance of resulting assignments? $\endgroup$ – Phylliida Feb 6 '16 at 6:16
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Feb 6 '16 at 13:30
  • $\begingroup$ @DanielleEnsign is the table always two rows of chairs, each of the same length? yes. other questions are answered in the problem. $\endgroup$ – morpheus Feb 6 '16 at 18:24
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note this generalizes to any number of rows of chairs around tables, of any size. $\endgroup$ – Phylliida Feb 6 '16 at 20:17
  • 1
    $\begingroup$ Is there a reason this answer hasn't been accepted? Was there something else you were looking for? $\endgroup$ – Phylliida Feb 7 '16 at 5:29
  • $\begingroup$ thanks for your answer. I haven't accepted it so that I could get more responses and since it didn't really give an efficient algorithm to solve the problem. The answer claims the problem is NP hard but there is no proof or reasoning behind it. $\endgroup$ – morpheus Feb 7 '16 at 19:38
  • $\begingroup$ Yes this is a formal proof... however that makes sense that an approximation algorithm would be useful too, I'll keep searching for you $\endgroup$ – Phylliida Feb 7 '16 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.