Top all-time · #2190
Carl de Marcken
Personal blog · demarcken.orgmathprogramming
Carl de Marcken writes de Marcken, a personal blog at demarcken.org about math and programming. Since 2007, 37 different Hacker News readers have linked it 43 times, most often “Computational Complexity of Air Travel Planning [pdf] (2003)”. No feed was found, so read it on the site itself.
Most-linked posts?
- Computational Complexity of Air Travel Planning [pdf] (2003)18 people · 22 mentions · first linked 2008-06-14
- Computational Complexity of Air Travel Planning6 people · 6 mentions · first linked 2008-12-15
- Computational Complexity of Air Travel Planning (2003)5 people · 5 mentions · first linked 2007-07-10
- /carl/papers/ITA-software-travel-complexity/img1.html3 people · 3 mentions · first linked 2007-07-11
What Hacker News says?
Here's the classic presentation people usually refer to when talking about flight pricing complexity. http://www.demarcken.org/carl/papers/ITA-software-travel-com... I'd love to know how Google's doing it - it's a really hard problem.
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Google Flight Search”Submitted Computational Complexity of Air Travel Planning [pdf] (2003) as a story · 76 points
HN discussionYou should first start reading these great slides from Carl de Macken (ITA Software co-founder, the thing that now powers Google Flights) http://www.demarcken.org/carl/papers/ITA-software-travel-com... …and then decide if you still want to pursue this.
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Google Flights will now tell you when fares will increase”Submitted Computational Complexity of Air Travel Planning (2003) [pdf] as a story · 74 points
HN discussionThe problem is that there is no single price at which you can fill the plane enough and cover expenses. Set the price too low and your plane fills up but your costs are not covered. Set your price too high and you have so many empty seats that even with the handful of people paying outrageous prices you can't cover the cost of crew, fuel, and ground services. This means you have to sell some tickets at low prices, t…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Google Flights will now tell you when fares will increase”Submitted Computational Complexity of Air Travel Planning (2003) [pdf] as a story · 72 points
HN discussionThe talk you're looking for is probably this: http://www.demarcken.org/carl/papers/ITA-software-travel-com...
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Google to Offer a Best Price Guarantee on Certain Flights”Submitted Computational Complexity of Air Travel Planning as a story · 30 points
HN discussion"The search engines run on databases of flights, prices, and seat availability, provided electronically over private networks by the 800 or so airlines of the world. The data is not directly available to the general public and access often must be negotiated with individual airlines. Flight data is updated daily or occasionally more frequently in the case of unexpected cancellations. Prices are updated about ten tim…
Comment linking /carl/papers/ITA-software-travel-complexity/img1.html
on “Google 20% time volunteers have been rewriting the ITA Matrix flight search app”Submitted Computational Complexity of Air Travel Planning as a story · 17 points
HN discussion> The software that ITA developers that makes them different from the rest Classic paper by Carl de Marcken, co-founder and former CTO of ITA Software, elaborating the unique domain problems of air travel planning: "Computational Complexity of Air Travel Planning" http://www.demarcken.org/carl/papers/ITA-software-travel-com...
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Google agrees to buy ITA Software for $700 million”Submitted Computational Complexity of Air Travel Planning (2003) as a story · 5 points
HN discussionThis is a good presentation about the complexities in creating and pricing itineraries: http://www.demarcken.org/carl/papers/ITA-software-travel-com... Most companies don't want to take on this complexity, so they outsource it. The companies that provide this service, like ITA, tend to charge more money for more expensive queries, like multi-day searches, so most online search companies will only let you do the chea…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Get away with Google Flights”Submitted Computational Complexity of Air Travel Planning (2003) as a story · 4 points
HN discussionOne of the founders of ITA Software, which became Google's flight search, discussed some interesting issues in airline fare search [0]. I don't have enough of a CS background to fully understand all of this, but the message is pretty clear: it's complicated. There was also an HN thread from 2012 discussing ITA's use of Lisp.[1] [0] http://www.demarcken.org/carl/papers/ITA-software-travel-com... [1] https://news.ycom…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Ryanair, Hamiltonian Cycles, and using graph theory to find cheap flights (2018)”Submitted Computational Complexity of Air Travel as a story · 4 points
HN discussionITA's strength isn't data, it's algorithms. Finding the best flight is not just NP-complete, it's uncomputable. In practice, even a lot of sub problems are NP-complete. http://www.demarcken.org/carl/papers/ITA-software-travel-com... People think the problem is a graph search problem of finding the shortest path. But that's actually the easiest part of the problem. It turns out that prices aren't attached to individu…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.html
on “Google acquires ITA Software”Submitted Computatational complexity of air travel planning [pdf] as a story · 3 points
HN discussionI answered part of this question earlier at http://news.ycombinator.com/item?id=1473748 The thing to understand is that the airlines publish data that ITA uses. The problem is that it takes an incredible amount of engineering effort and algorithm smarts to go from 'published airline data' to 'this is the cheapest flight from BOS to LAX on 4/20'. ITA does have competitors; historically those competitors offered much…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.html
on “Google acquires ITA Software”Submitted Computational Complexity of Air Travel Planning as a story · 1 points
HN discussionLink should be: http://www.demarcken.org/carl/ But yes... I agree!
Comment linking /carl/
on “Is This The Future of The Airline Website?”Submitted Computational Complexity of Air Travel Planning (2003) as a story · 1 points
HN discussionYou should read his paper showing that (under various unrealistic assumptions) travel planning is undecidable: http://www.demarcken.org/carl/papers/ITA-software-travel-com...
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “Is This The Future of The Airline Website?”Submitted Complexity of flight search as a story · 1 points
HN discussionWhile you persist on your belief system, a big, award-winning code controlled the NASA Deep Space One out in space for several days. Done 100% in a dynamic language. A really big and complex program, is right now doing airline planning for over 800 companies, taking into account 4000 airports. To get an idea of the complexity look at this pdf: http://www.demarcken.org/carl/papers/ITA-software-travel-com... Both exam…
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “LambdaNative – Cross-platform mobile apps in Scheme”A handy reminder of why flight search is Hard with a capital H: http://www.demarcken.org/carl/papers/ITA-software-travel-com... (ITA being the company purchased by Google)
Comment linking /carl/papers/ITA-software-travel-complexity/img0.html
on “Google flights”This is probably unsatisfying, but it's where I read about it: http://www.demarcken.org/carl/papers/ITA-software-travel-com... ToC: http://www.demarcken.org/carl/papers/ITA-software-travel-com... You could email the author and ask him, he seems to know.
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.html
on “First Sale Under Siege: If You Bought It, You Should Own It”http://www.demarcken.org/carl/papers/ITA-software-travel-com... from http://news.ycombinator.com/item?id=1479107
Comment linking /carl/papers/ITA-software-travel-complexity/img1.html
on “How we buy plane tickets and why it's ruining air travel”Classic ITA paper that shows you the complex problems they deal with: http://www.demarcken.org/carl/papers/ITA-software-travel-com...
Comment linking /carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
on “ITA Software's Hiring Puzzles”From the great presentation linked: http://www.demarcken.org/carl/papers/ITA-software-travel-com... > Amazingly, the graph diameter is often as high as 20: there are airports that can take 20 flights minimum to get between I wonder if that's still true. It's hard to imagine. And just the thought of having to optimize that search function made my cortisol levels spike a bit.
Comment linking /carl/papers/ITA-software-travel-complexity/img4.html
on “A flight search engine that combines flights from different airlines? (2014)”
