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/

SpaceX catches the Starship to end Flight 15

https://www.spacex.com/launches/starship-flight-15
604•ls612•3h ago•417 comments

Lovable apps expose passport details and more than 200K private messages

https://www.crissyfield.de/research/lovable-en/
611•armcat•7h ago•255 comments

How did Woz write the Apple 1 BASIC before building the computer?

https://retrocomputing.stackexchange.com/questions/17957
63•Skyfall106•2h ago•22 comments

A family tree of software job titles

https://zwischenzugs.com/2026/11/03/a-family-tree-of-software-job-titles/
192•umerf•7h ago•91 comments

KDE: The documentary [video]

https://tube.kockatoo.org/w/fFinNHfanLT7aBEb2B8y4c
369•mrkn1•11h ago•79 comments

Nvidia deliberately kept GPU prices high through circular financing deals

https://www.techspot.com/news/114558-nvidia-deliberately-kept-gpu-prices-high-through-circular.html
117•madihaa•2h ago•60 comments

PyPI's redesigned project pages with clearer security signals are now live

https://blog.pypi.org/posts/2026-11-06-ui-updates-complete/
198•rbanffy•9h ago•90 comments

Why get an expensive Pi when I have an old phone?

https://so.long.thanks.fish/why-pi-when-i-have-an-old-phone/
497•casi•4d ago•280 comments

Show HN: DeepSeek V3 in ~200 lines of pure Jax

https://github.com/Vaibhaav-Tiwari/deepseek-v3-jax
158•VaibhaavTiwari•9h ago•8 comments

Seagate's new hybrid drive raises some old questions

https://arstechnica.com/gadgets/2026/11/seagate-resurrects-the-ssd-hdd-hybrid-drive/
65•PaulHoule•3d ago•37 comments

Advancing science and engineering with Antigravity's /teamwork

https://research.google/blog/advancing-science-engineering-with-antigravitys-teamwork-feature/
158•acossta•11h ago•36 comments

'Grey Rocking': The Life-Improving Power of Being Really, Really Boring (2021)

https://www.esquire.com/uk/life/a38473153/grey-rock-technique-being-boring/
87•NaOH•2d ago•50 comments

Reverse engineering a vintage diode-transistor logic chip

https://www.righto.com/2026/11/signetics-st680a-dtl-nand.html
90•dverlaeckt80•6d ago•5 comments

Generative AI uses more energy on non-English text

https://news.umich.edu/generative-ai-uses-more-energy-on-non-english-text/
173•DeepLogin•4d ago•98 comments

Testing a trash can Faraday cage

https://www.jefftk.com/p/testing-a-trash-can-faraday-cage
62•torutofu•2d ago•55 comments

Write your own kernel optimiser

https://blog.csongor.co.uk/cachet-grids-and-tiles/
11•speckx•4d ago•0 comments

LinkedIn, Monster take down over 1000 fake job postings after CBC investigation

https://www.cbc.ca/news/canada/linkedin-monster-take-down-over-1-000-fake-job-postings-after-cbc-...
171•gnabgib•5h ago•90 comments

Project Zero will disclose vulnerabilities 90 days after reporting

https://projectzero.google/2026/11/disclosure-policy.html
145•hacb•13h ago•35 comments

L3Harris statement on the Nov. 13 ground stop

https://www.l3harris.com/newsroom/press-release/2026/11/l3harris-statement-nov-13-ground-stop
53•taspeotis•2h ago•21 comments

Show HN: A terminal-native idle factory game, written in Rust with ratatui

https://gitlab.com/snipedbywifi/terminactory
132•snipedbywifi•10h ago•27 comments

The Sicilian Citrus Family Tree

https://www.notesfromtheroad.com/europa/citrus-family-tree.html
25•wmchen•3d ago•4 comments

Oxford Molecular Motors

https://www.physics.ox.ac.uk/research/group/oxford-molecular-motors/research/bacterial-flagellar-...
4•handfuloflight•3d ago•1 comments

Tech companies are trying to shift the concept of privacy again

https://www.eff.org/deeplinks/2026/11/tech-companies-are-trying-shift-entire-concept-privacy-again
449•gslin•12h ago•170 comments

A visual explanation of reinforcement learning

https://aatishb.com/myriad/how-brains-learn/
115•aatish•11h ago•6 comments

Demystifying phone unlocking tools: A technical overview

https://osservatorionessuno.org/blog/2026/05/demystifying-phone-unlocking-tools-a-technical-overv...
69•iloveyoutwo•10h ago•5 comments

Let's Write a PostScript Interpreter

https://beyondloom.com/blog/postscript.html
103•RebelPotato•1d ago•17 comments

Italy fines Meta $887M over Android users' data access

https://www.reuters.com/world/italy-fines-meta-887-million-over-android-users-data-access-2026-11...
321•giuliomagnifico•11h ago•215 comments

Show HN: Fursoy – Out-of-order RV64IMAFDV core in SystemVerilog (Linux 6.6)

https://github.com/FURSOY/fursoy-cpu
66•fursoy•10h ago•21 comments

Dartmouth (Guarini) will not admit math PhD cohort this year

https://www.thedartmouth.com/article/2026/11/gandhi-fagell-guarini-will-not-admit-math-ph-d-cohor...
67•sebg•5h ago•25 comments

Chinese frontier AI models carry the fingerprint of export-controlled GPUs

https://unemploymentlabs.com/checkpoint-forensics
371•firloop•2d ago•161 comments