Given seats and stations, and assuming that is not less than the number of passengers, the seat reservation problem seeks to determine an online seat allocation scheme that maximizes ticket revenue, where every ticket has the same price. The scheme must be fair, namely, every passenger is allocated to a seat.

This paper examines the seat reservation problem in detail. Both deterministic and random schemes are investigated. The problem can be directly expressed in terms of interval graphs, where the interval is from to , and seat assignment for a subinterval to passenger assigns color to that subinterval. There is a known offline polytime algorithm to do this. The goodness measure is a competitive ratio, , where e Opt + , and Opt is optimal revenue for an oblivious offline adversary, and is an absolute constant. Obliviousness means that the adversary constructs its scheme before allocation begins. Note that a lower bound is obtained through worst-case analysis, while an upper bound is obtained by constructing an adversary.

The proof techniques are highly specialized to the problem, and somewhat intricate. The interested reader should consult the paper for these. Among other interesting results, results are presented for the case = , which seems to be less well motivated than the general case, so I’ll restrict myself to > . Any online algorithm achieves e . If e and a mod , then any deterministic online scheme has the upper bound d + , which is asymptotically sharp for of even modest size, and so asymptotically, deterministic schemes obey d . Random schemes obey d when a mod , and generally d .