The ACO Seminar (2015–2016)

Nothing seems more boring and mundane than the process of boarding an airplane. Airlines have tried to optimize boarding time by making announcements of the form "passengers from row 40 and above are now welcome to board" or "passengers in group 3" are now welcome to board, or the recent policy "Passengers with no overhead bin carry on luggage may board first".

From an algorithmic point of view airplane boarding is rather curious. Usually we have a problem and we devise an algorithm for solving it. In airplane boarding, the algorithm is simple. 200-400 passengers, get in line, proceed to the airplane and sit down, providing a distributed method of computing something, but what is the thing being computed, what type of problem are we solving?

In the talk, we will try to answer this question and as time permits, map the relations of airplane boarding to queueing theory, scheduling of I/O in disk drives, relativity theory, combinatorics, probability, optics, random matrices, computational geometry, differential geometry, lasers, surface growth models, modular symmetries and more.

In particular, I will try to explain some recent work providing a strong relation between the "Passengers with no overhead bin carry on luggage may board first" policy and certain queues known as SITA queues which were studied extensively by (among others) M. Harchol-Balter and A. Scheller-Wolf.