Now boarding row N

I am at gate C21 at Houston Intercontinental, en route to San Antonio. The flight is late and overbooked; there’s a crowd of hopeful standbys at the podium. The first-class plutocrats are already aboard, and now the rest of us are filing on, one section at a time. “Passengers in rows 25 to 29 are invited to board the aircraft” was the first announcement. Ten minutes later they called for rows 20 to 29. My boarding pass is for seat 14B.

Frequent flyers understand the rationale behind this routine. By filling the airplane from back to front, the theory goes, passengers sitting in the rear won’t have to wait in the aisle while the couple in 8-A and 8-B stow their luggage, fetch blankets and pillows, argue over who gets the window, settle into their seats, get up again to retrieve a book from the overhead bin, and then discover that their tickets are actually for 18 A and B.

A recent paper reveals the awful truth. The airlines’ last-shall-be-first strategy doesn’t work. We might be better off lining up in random order.

The paper, posted in the physics division of the arXiv, is by Eitan Bachmat, Daniel Berend, Luba Sapir and Natan Stolyarov (all of Ben-Gurion University) and Steven Skiena of the State University of New York at Stony Brook. The authors call forth quite a dazzling array of high-powered mathematical tools in the course of their analysis. The geometric context of the problem turns out to be a two-dimensional spacetime with a Lorentz metric; there’s a combinatorial element to the story, involving longest increasing subsequences; from there, I’m afraid it gets even deeper, and at one point we find ourselves dealing with “the normalized discrepancy of the largest eigenvalue of an N x N matrix in the Gaussian unitary ensemble (GUE).”

For all that, the ultimate outcome is clear enough, and it even makes intuitive sense. Suppose there are 29 rows of seats with six seats per row, and the flight is full. Suppose further that the last-first policy can be enforced perfectly, so that all the passengers in row 29 are first in line, followed by those in row 28, and so on. Boarding should be a completely orderly process, with everyone sitting down after the minimum possible delay, no? No. The problem is that no one in rows 1 through 28 can reach their row until at least some of the six passengers in row 29 seat themselves. Then, everyone forward of row 28 has to wait for the next six people to sort themselves out. Under this regime the total boarding time is proportional to N, the total number of passengers. Lining up in random order offers a good chance of getting everyone aboard in time proportional to the square root of N.

If we insist on trying to find an improvement over the random result, we might be better off lining up with all the window seats first, then the middles and finally the aisles—a scheme that some airlines are apparently trying, with loading “zones.” Another algorithm for an airplane with 29 rows of six seats each would line the passengers up according to row number in this sequence: 29 23 17 11 5 28 22 16 10 4…. Then the question becomes: Is the flying public ready for announcements of the form, “We are now boarding all rows N where N is congruent to 5 modulo 6″?

Addendum: Once I finally got aboard, I discovered a further complication: The airplane didn’t actually have 29 rows. My seat in 14B was directly behind row 12. Evidently, Continental Airlines suffers from triskaidekaphobia.