First page Back Continue Last page Overview Graphics
Complexity Review
Even the most basic subproblems are provably hard
Proofs reflect the real algorithmic challenges we have experienced
Complexity proofs are harder than they look
- electronic format for fare rules is complicated but very limited
Heuristics risky: airlines can change their fare and rule structures instantaneously; sometimes deliberately complicate space
Order-of-growth is a serious issue:
- 30,000,000 flights in database
- 150,000,000 fares in database
- 10,000 to100,000,000 flight combinations for a round-trip
- 10,000 to100,000,000 fare combinations for each flight combo
- much worse for multiple passengers
Notes:
What do these proofs tell us? The first two proofs show that even if all but one dimension of the problem are fixed, the problem remains at least NP-hard. That is, each dimension of the search is hard by itself. And the proofs themselves reflect fairly well the algorithmic difficulties in solving the problem, especially the proof that even if flights are fixed, the search for fare combinations is NP-hard, since the types of restrictions used in that proof are quite commonly encoded by the airlines. The proofs are slightly more difficult than they look here, only because it is difficult to find the machinery in the airline industry's complicated but inexpressive rule language to express the constraints necessary for reductions.
The EXPSPACE and unsolvability proofs are harder to interpret. They depend on very unusual constructions and lengthy tickets. They should perhaps be seen as supporting evidence for the power of the airlines' pricing system, that reinforces the simpler results. The fact that they depend only on very simple rule systems also suggests that complexity can arise from the combination of independently simple pricing rules.
A normal response to a problem that is theoretically hard is to search for heuristics that perform well in practice. One of the challenges to the travel planning problem is that the airlines can update their fares and rules 10 times a day, potentially changing the structure of the search problem in an instant: any carefully tuned system could be destroyed by a new vice president of marketing at an airline on his or her first day of work.
One might hope that problem sizes are small enough in practice to be solvable, but the N’s in algorithmic complexity can be big. There are 30 million flights a year, 150 million published fares, 10,000 to 100,000,000 or more flight combinations for a simple round trip journey, 10,000 to 100,000,000 or 100,000,000,000,000 or more fare combinations for a fixed set of flights, and exponentially worse for multiple passengers.
[As a minor aside, it is not entirely clear whether the proofs that these constrained problems are NP-hard should more precisely read NP-complete; that is, it is not certain whether the constrained problems are in NP. To prove membership one must show that potential solutions can be fully checked in time polynomial in their size, and the problem specification is too complex, and vague, to ever mathematically prove such a result.
But formal proof aside, polynomial time evaluation of solutions is almost certainly possible if one does not consider price. To validate the price of an international trip requries performing IATA checks, and whether these can be run in polynomial time is not obvious, since IATA checks compare the solution's fares against other potential sets of fares, and the complexity of this process turns on imprecise details of the IATA check specification. On the whole it is probably reasonable to assume that polynomial time evaluation of solutions, including price, is possible, and that the constrained problems are NP-complete.]