Wedding table problem
Here's the old ancient wedding table problem that each man inevitably has to solve on his way to honeymoon.
Research on the topic shows that some philosophers simplify this problem to set partitioning problem (not sure if they were on any wedding, or are they just dinning philosophers). Whereas others assign the problem to the social nature of participants. But I guess that for all my readers it's obvious that this is strictly mathematical subject and should be analysed from the algorithms perspective.
Problem statement:
Newlyweds are holding a party of n guests, where 2m of them comes in couples and the rest comes single. There's one long table with n chairs, split equally on both sides and each guest needs to have a chair assigned. Each couple has to together. Guests sitting next to each other, or on the opposite sides of the table are in talking range. There's a graph G(V, E), where each vertex represents a couple or single guest and each edge represents an acquaintance relationship between guests. Guests should have chairs assigned in such a way that the maximum acquaintances will be sitting in talking range.
Input data:
n
m
v1 e11 e12 e13.. e1n1
v2 e21 e22 e23.. e2n2
...
vm em1 em2 em3.. emnm
...
v(n-m) e(n-m)1 e(n-m)2... e(n-m)n(n-m)
where e11, e12, ... e(n-m)n(n-m) are in v1..v(n-m);
n1, n2, ... n(n-m) are in 0..(n-m);
Output data:
Example:
in:
5 - n = 5 guests
2 - m = 2 couples
1 2 - first couple is acquainted with 2nd couple
2 1 - and vice versa
3 - single has no acquaintances
out:
Couple one is opposite to couple two and single guest sits at the remaining chair.
There are modifications to this problem, such that the table is not straight, but e.g. T-shaped, L-shaped, E-shaped, round or other. This affects the talking range definition. In some situations, acquaintance graph G is replaced with avoid graph Gavoid(V,Eavoid) where talk range must not cover the avoid edges. In an extreme case Ghate(V,Ehate) graph models situation where distance between guests on the graph edges must be maximized. Most practiced philosophers solve the problem that includes all three relationships.
Typical problems are of size n > 50, so be careful with the computational complexity of your solution!
Research on the topic shows that some philosophers simplify this problem to set partitioning problem (not sure if they were on any wedding, or are they just dinning philosophers). Whereas others assign the problem to the social nature of participants. But I guess that for all my readers it's obvious that this is strictly mathematical subject and should be analysed from the algorithms perspective.
Problem statement:
Newlyweds are holding a party of n guests, where 2m of them comes in couples and the rest comes single. There's one long table with n chairs, split equally on both sides and each guest needs to have a chair assigned. Each couple has to together. Guests sitting next to each other, or on the opposite sides of the table are in talking range. There's a graph G(V, E), where each vertex represents a couple or single guest and each edge represents an acquaintance relationship between guests. Guests should have chairs assigned in such a way that the maximum acquaintances will be sitting in talking range.
Input data:
n
m
v1 e11 e12 e13.. e1n1
v2 e21 e22 e23.. e2n2
...
vm em1 em2 em3.. emnm
...
v(n-m) e(n-m)1 e(n-m)2... e(n-m)n(n-m)
where e11, e12, ... e(n-m)n(n-m) are in v1..v(n-m);
n1, n2, ... n(n-m) are in 0..(n-m);
Output data:
_____
vout1 [o o] vout2
vout1 [o o] vout2
... [o o] ...
... [o___o] voutn
Example:
in:
5 - n = 5 guests
2 - m = 2 couples
1 2 - first couple is acquainted with 2nd couple
2 1 - and vice versa
3 - single has no acquaintances
out:
_____
1 [o o] 3
2 [o o] 4
5 [o___o]
Couple one is opposite to couple two and single guest sits at the remaining chair.
There are modifications to this problem, such that the table is not straight, but e.g. T-shaped, L-shaped, E-shaped, round or other. This affects the talking range definition. In some situations, acquaintance graph G is replaced with avoid graph Gavoid(V,Eavoid) where talk range must not cover the avoid edges. In an extreme case Ghate(V,Ehate) graph models situation where distance between guests on the graph edges must be maximized. Most practiced philosophers solve the problem that includes all three relationships.
Typical problems are of size n > 50, so be careful with the computational complexity of your solution!
.png)
Jacek
ReplyDeleteYou might like to look at out http://www.perfecttableplan.com/ software. It solves this problem using a genetic algorithm. While it can't guarantee a optimal answer, it can usually get pretty close quite quickly. It can also handle 3000+ guests.