What's the best reserved seat sorting algorithm?

Question

I'm trying to find the best algorithm for the following sorting problem.

There are N = K × M seats in an auditorium with one aisle, K rows, and M seats per aisle. The assumption is made that K is a bigger than M, but I don't think that's very important. There are N people that are in bijection with the seats (assigned seats). Assuming that people don't like waiting, what's the fastest way to line them up to get them all in their seats as quickly as possible?

I ran some simple experiements (using random permutations) and it seemed that letting them line up randomly is faster than having the people in the front third (further down the aisle) line up first, then the middle third, then the back third. That seems wrong to me.

I'm writing this in MatLab if that matters at all. Any ideas or answers?

Answer 1

There is a very nice article by Bachmat, Berend, Sapir, Skiena and Stolyarov entitled Analysis of airplane boarding via space-time geometry and random matrix theory that models this exact problem for airplane boarding. From their abstract:

We show that airplane boarding can be asymptotically modeled by 2-dimensional Lorentzian geometry. Boarding time is given by the maximal proper time among curves in the model. Discrepancies between the model and simulation results are closely related to random matrix theory. We then show how such models can be used to explain why some commonly practiced airline boarding policies are ineffective and even detrimental.

The conclusions of the paper are:

• BEST: Window-Middle-Aisle
• NEAR OPTIMAL: Random Boarding
• REALLY BAD: Back-to-Front

For your set-up, I think this means you should ignore how far down the aisle the people are and instead focus on how far from the aisle they are. This model also accounts for time to store luggage, so you may need to adjust that somewhat for your situation. In any event, I think this confirms what you are finding through your model.