frontpage.
newsnewestaskshowjobs

Open Source @Github

fp.

Open in hackernews

Computational Complexity of Air Travel Planning [pdf] (2003)

http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf
76•rochoa•1y ago

Comments

buildsjets•1y ago
This is well over 20 years old and is based on pre 9/11 flight data. I would suspect that a lot has changed since then. So proceed with no caution at all.
gwern•1y ago
Since these sorts of things usually only get more and more complex over time, I would guess that it's all still true, but much more so.
throw0101b•1y ago
(2003)
throw0101b•1y ago
The PDF was produced by ITA, which famously used Common Lisp:

* https://en.wikipedia.org/wiki/ITA_Software

From 2001, a message from the same author as the linked paper:

> (Here's an email Carl de Marcken of ITA Software sent to a friend, describing their experiences using Lisp in one of the software industry's most demanding applications.)

* https://www.paulgraham.com/carl.html

Qem•1y ago
Are there any public, open, comprehensive datasets on flights?
dieselerator•1y ago
> Are there any public, open, comprehensive datasets on flights?

Airlines and commercial aviation operators schedule their own flights. That is a dynamic schedulle. So, perhaps there is no "comprehensive data set".

However, FlightAware makes publicly available scheduled and completed flight data over many routes in the USA. You can search by route and get a list of flights.

Flight information includes filed departure time, route of flight, and speed. For completed flights actual time, altitude, and route is shown. For example, a search on the route Dallas/Fort Worth to Austin lists 45 flights.

I hope that helps.

foundart•1y ago
A very interesting dive into, as the title says, the computational complexity of air travel planning. Graph algorithms with lots of complexity added due to the wide variety of fare conditions that airlines have dreamt up over the years.

The article may be from 2003 but I would call it an evergreen. While I imagine some of the details have changed since then, I suspect that the complexity has only grown since then.

foundart•1y ago
It makes me wonder: Would an airline that drastically simplified its fares be more likely to appear in flight search results?

Simplifying the fares would make it less computationally expensive and, in theory, could take fewer steps to answer a flight planning query.

Imagine a flight search planner that, say, fanned out N airline-specific workers when handling a planning query and then displayed to the user whatever results it got back within some time limit. If FooAir had simple fares, the FooAir searcher would likely run faster than searchers for other airlines. Thus it would be more likely to return results for more queries, assuming the deadline is fairly tight because of usability metrics. (People don't tend to stick around waiting for slow results.)

sjburt•1y ago
At least a few years ago (~2014), the fare search was actually nearly instant, but all major airfare search sites added a delay because customers had the impression they were getting a better deal when they had to wait. It seems like the delay has been dialed back lately.
teleforce•1y ago
This is a very popular article that get submitted every now and then (nearly every year) [1].

I think this kind of problem would be a very nice for logic, optimization and constraint programming that probably can be solved with modern tools like Google OR-Tool or Monash University MiniZinc [1],[2],[3].

[1] Past:

https://hn.algolia.com/?query=Computational%20Complexity%20o...

[2] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]:

https://www.youtube.com/live/TknN8fCQvRk

[3] Google OR-Tools:

https://developers.google.com/optimization

[4] MiniZinc:

https://www.minizinc.org/

Reverse Engineering My Coway Air Purifier to Ditch the Cloud

https://scottjg.com/posts/2026-11-11-reverse-engineering-my-coway-air-purifier-to-ditch-the-cloud/
185•scottjg•17h ago•41 comments

Doomsday: Friday, 13 November, A.D. 2026 (1960)

https://www.science.org/doi/10.1126/science.132.3436.1291
298•voxleone•3h ago•197 comments

Why Zig over C for Systems Programming

https://www.mtsoukalos.eu/2026/11/why-zig-over-c-for-systems-programming/
80•torutofu•1h ago•26 comments

Jensen Huang resigns

https://apnews.com/article/nvidia-megaspeed-china-singapore-huang-5403f152a601cf82ce939f1d24fffa0f
3832•lldb•1d ago•3300 comments

A technical vision for the Haskell ecosystem

https://discourse.haskell.org/t/a-technical-vision-for-the-haskell-ecosystem/15078
27•cosmic_quanta•1h ago•7 comments

Elevated errors on claude.ai, Claude Code, and platform.claude.com

https://status.claude.com/incidents/nn11wk485zfn
396•__vivek•5h ago•329 comments

U.S. October PPI Rises 6.5% YoY, Highest in Nearly Four Years

52•moonypto•1h ago•14 comments

Palmfrets, Minnesota guitarist's invention, strikes a new chord

https://www.echopress.com/business/minnesota-guitarists-invention-strikes-a-new-chord
10•bookofjoe•48m ago•3 comments

IceWM

https://ice-wm.org/
298•inatreecrown2•11h ago•153 comments

Lonewolf 0.3 – A standalone XMPP server written in Rust

https://github.com/lonewolf-im/lonewolf/releases/tag/v0.3.0
14•ortuman•1h ago•4 comments

Rust 1.100

https://blog.rust-lang.org/2026/11/12/Rust-1.100.0/
801•mbStavola•21h ago•293 comments

Brave Search API now accepts agentic payments via the x402 protocol

https://brave.com/blog/search-api-agentic-payments/
204•sjdh76•12h ago•113 comments

The 42-Year Journey to Bring 'Neuromancer' to the Screen

https://www.wired.com/story/exclusive-apple-tv-neuromancer-creator-interviews/
47•Brajeshwar•1h ago•25 comments

US university students tell surveillance cameras to Flock off

https://www.theguardian.com/technology/ng-interactive/2026/nov/13/universities-drop-flock-camera-...
29•beardyw•1h ago•1 comments

Show HN: My $300 embroidery machine needed a subscription, so I built my own app

https://github.com/simpsoka/zigzag
657•simpsoka•22h ago•218 comments

Gemini 4 Hydrogen and Orchestrator

https://antigravity.google/blog/gemini-4-hydrogen-in-google-antigravity/
467•jonbaer•21h ago•144 comments

AI Is Destroying the Trust Between Writers and Readers

https://www.theatlantic.com/books/2026/11/ai-literary-scams-amazon/689391/
122•FinnLobsien•4h ago•30 comments

Former Nvidia CEO Huang had a relationship with a second employee, sources say

https://www.reuters.com/technology/former-nvidia-ceo-huang-had-relationship-with-second-employee-...
381•jbredeche•20h ago•412 comments

Dwarf planet candidate appears which takes roughly 280 years to orbit our sun

https://www.smithsonianmag.com/smart-news/astronomers-found-a-mysterious-object-orbiting-far-beyo...
361•cybermango•20h ago•156 comments

Edge0-145B: Frontier AI Capabilities on Your Own Computer

https://edge0.ai/blog/introducing-edge0-145b-frontier-ai-capabilities-on-your-own-computer
306•sroussey•16h ago•91 comments

The Dawn of the Data Intelligence Engineer

https://motherduck.com/blog/the-data-intelligence-engineer/
101•jonbaer•6h ago•68 comments

EU Digital Identity Wallet rollout: every EU state on one board

https://myid.ie/business/eu-digital-wallet-tracker/
18•mooreds•58m ago•0 comments

I'm making LLMs work on small and old devices

https://github.com/hyperionaidev/smolmaxxing/
433•mrashad74•1d ago•165 comments

Service degradation on Microsoft 365

https://status.cloud.microsoft/
1080•dkpk•21h ago•909 comments

US test reactor cleared for operations

https://www.world-nuclear-news.org/articles/us-test-reactor-cleared-for-operations
24•PaulHoule•2h ago•7 comments

Foundation Models framework

https://developer.apple.com/foundation-models-framework/
247•kermatt•18h ago•33 comments

Switcher (2004)

https://folklore.org/Switcher.html
123•sammatilda•12h ago•38 comments

Abandoned Quake 4 expansion finished by modders and now playable

https://www.moddb.com/mods/openq4/downloads/openq4-0141-windows-x64
296•klaussilveira•1d ago•115 comments

Turning a 22-year-old Postgres type-confusion primitive into RCE

https://mehmetince.net/part-3-6-how-i-ended-up-turning-a-22-year-old-postgresql-type-confusion-pr...
224•ozirus•21h ago•40 comments

Eli Lilly CEO pushes back on Dario Amodei's medical claims

https://garymarcus.substack.com/p/breaking-eli-lilly-ceo-becomes-latest
231•Noaidi•2h ago•285 comments