2006_02_01_archive

I didn't realize finding airfares was that hard.

But it does make me feel a lot better. From a talk announcement over

at [LB,UB]:

At any moment there are between 2,000 and 10,000 commercial

airliners in the sky, part of a dense network that provides, for

example, more than 100,000 practical paths from Boston to the San

Francisco area every day. At its core, finding a sequence of

flights that meets the user's stated time constraints is a

path-planning problem which can be solved with well-known

techniques. But the airfare search problem is much more complex

than that. In fact, the airlines' price structure is so rich that

finding the cheapest price for a simple round-trip journey is in

the general case provably undecidable. Even if one bounds the size

of solutions to a small number of flights there may be more than

1020 reasonable answers to a simple travel query. The problem is

compounded by the fact that airline revenue management systems are

constantly and dynamically adjusting the prices for each flight

along a discretized scale.

Seriously though, how is this even possible ? There are a finite

number of routes at any given time, and i am assuming that no one pays

me to fly (I'm ignoring voluntary bumps of course), so the total path

length must increase if I take longer and more byzantine routes...

Update (2/3): Michael Mitzenmacher indicates that there is more to the

problem that meets the eye. In fact, he goes further:

If you have any smart students who are looking for a job in a

"real-world" company, I'd strongly recommend they look at ITA

software. Obviously I've drunk the Kool-Aid, but I think they'll

continue to be an innovative, leading company in the travel space.

And heck, how many companies do you know that even think to

advertise themselves by giving a talk about the undecidable

problems they are tackling!

Categories:

* optimization

Posted by Suresh at 2/02/2006 02:05:00 PM 8 comments Links to this

post

STOC Numerology

Via Piotr via Sariel, I hear that there were 288 submissions to STOC

this year (and 78 accepted), making a net acceptance of rate of 27.1%.

Comparing this to Jeff's charts from [DEL: last :DEL] this year, it