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/

The Secret ThinkPad Powerbutton Code to Bring Dead Laptops Back to Life (2007)

https://masnick.com/posts/the-secret-thinkpad-powerbutton-code-to-bring-dead-laptops-back-to-life/
170•sammatilda•4h ago•76 comments

Many of Amazon’s Black Friday and Cyber Monday “Deals” Offered No Savings

http://groundworkcollaborative.org/news/amazons-decoy-deals-groundwork-investigation-reveals-near...
304•DeepLogin•2h ago•161 comments

How to make almost anything

https://pub.cba.mit.edu/863.26/site/
625•o4c•10h ago•103 comments

Universal XSS in uBlock Origin from website-driven element picker

https://iter.ca/post/ubo-uxss/
522•zaik•14h ago•148 comments

What is w2rt6byl5nf1opmc-a.com?

https://jack.cab/blog/siterate
244•dverlaeckt80•2h ago•103 comments

Interpreting claims that a theorem is correct because it was checked in Lean

https://xenaproject.wordpress.com/2026/11/12/and-the-proof-is-checked-in-lean/
184•matt_d•8h ago•69 comments

OOS – an open operating system for the Rigol Scopes

https://www.eevblog.com/forum/testgear/oos-an-open-operating-system-for-the-rigol-scopes/
74•qwezxcrty•2d ago•26 comments

Nvidia Was in Trouble Before the Jensen Huang Mess

https://www.wired.com/story/nvidia-was-already-in-trouble-before-the-jensen-huang-mess/
34•Brajeshwar•1h ago•10 comments

Show HN: OpenTodo – a self-hosted, local-first task manager in one Go binary

https://github.com/OpenTodoApp/OpenTodo
14•pixari8383•3h ago•7 comments

Researchers track whole body movement with just a smartwatch

https://news.cornell.edu/stories/2026/11/researchers-track-whole-body-movement-just-smartwatch
141•PaulHoule•2d ago•44 comments

Qwen4-Max

https://qwen.ai/blog?id=qwen4-max
758•ilreb•14h ago•382 comments

What's Next for Nvidia?

https://steveblank.com/2026/11/15/whats-next-for-nvidia/
394•zdw•16h ago•501 comments

Old Bitly links are being hijacked

https://ransomnews.com/burger-king-tweet-bitly-link-hijack-2026/
350•hspeiser•18h ago•180 comments

Winudf – DVD / BluRay driver for DOS, Windows 1.x – 3x / 95 / 98 / ME

https://github.com/ages2001/WINUDF
62•Oxodao•8h ago•6 comments

Coffeehouses and the Rise of Science [pdf]

https://www.monirbounadi.com/Bounadi_JMP.pdf
134•Michelangelo11•5h ago•82 comments

Tor Project Issues Rapid-Response DoS-Defense Fix Amid Sustained DDoS Attack

https://forum.torproject.org/t/security-release-0-4-9-17/22454
216•aillia•16h ago•55 comments

Show HN: ThingStudio, Node-RED style programming for microcontrollers

https://thingstudio.net/
22•mkarliner•5d ago•3 comments

Protomaps: Self-hosting map tiles has gotten cheap and easy

https://bruceroettgers.eu/blog/protomaps/
427•bcye•21h ago•75 comments

Handwriting, as a Font

https://ductus.sorenblank.com
400•coinfused•20h ago•70 comments

Nature-Based Sanitation. Cihuatlán: A Large-Scale Artificial Wetland

https://revista.unaminternacional.unam.mx/en/nota/12/saneamiento-basado-en-la-naturaleza-cihuatla...
4•bryanrasmussen•2d ago•1 comments

A short explainer on how El Niño works [video]

https://www.youtube.com/watch?v=7_JF3etiAv8
283•nharada•22h ago•167 comments

Preserving 30 years of Salon journalism

https://blog.archive.org/2026/11/12/preserving-30-years-of-salon-journalism/
192•CharlesW•17h ago•53 comments

The Lasting Influence of John Berger

https://www.newyorker.com/magazine/2026/11/16/john-berger-a-life-tom-overton-book-review
50•prismatic•4d ago•4 comments

Crows make decisions faster than we can

https://www.nytimes.com/2026/11/15/science/birdbrain-crows-birds-research-decision.html
283•gumby•22h ago•189 comments

Exact Gradients Through a BRep Kernel

https://muni.works/research/vcad
36•ecto•2d ago•12 comments

Do we still have to denormalize? Have your schema and search it too

https://www.paradedb.com/blog/joins
106•philippemnoel•3d ago•35 comments

Whistleblower accuses Pentagon over Iran strike on US base that killed 6

https://www.cnn.com/2026/11/15/politics/army-soldier-whistleblower-complaint
161•firefax•2h ago•40 comments

The Opportunivore's Dilemma

https://www.vqronline.org/essays/opportunivores-dilemma
9•NaOH•2d ago•9 comments

WebGL Flight Simulator with seed generated terrain

https://baron.by.dai.studio/
214•ranger_danger•20h ago•53 comments

A quest to create the perfect whiskey glass

https://www.nytimes.com/2026/11/13/dining/drinks/kurt-josef-zalto-whiskey-glass.html
85•Kaibeezy•2d ago•93 comments