5 ms·

From the great presentation linked: http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/img4.html http://www.demarcken.org/carl/papers/ITA-softw

by sho 2y ago

From the great presentation linked: http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/img4.html 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.

cozzyd 2y ago
I imagine it must be something like small Pacific island to small town in the Canadian far north or something...
- bluGill 2y ago
  Canada is too rich - there are more likely to be flights.
  - cozzyd 2y ago
    Yes probably Russian far north is more likely I guess!
- dmurray 2y ago
  The next line specifies: > typically this will be a small airport in Alaska or Canada to another small airport in Africa or Indonesia It's still mind blowing to me. Surely any Alaskan airport would be within 5 hops of Anchorage (or not have scheduled flights at all, fine, but that can't be the case here), likewise surely any Indonesian airport is within 5 hops of Jakarta, and Anchorage-Jakarta can certainly be done in 3 hops in a multitude of ways. But one of those assumptions is wrong by 7 hops! There aren't even that many airports to consider, the same presentation gives 4000 as the number included in the analysis. Maybe the graph topology is something like a series of tiny airports that each only connect to the next airport in the series, probably by the same flight that makes multiple stops (not unknown in island hopping, and maybe then in Alaska/Canada too). So you don't really board 20 planes but you do require 20 takeoffs and landings.
  - dmurray 2y ago
    Thinking about it, I bet you can prove this is the topology. If the graph is generally densely connected (almost all nodes have 3+ destinations) then the diameter can't be that high compared to the size of the graph. Proof left to the reader. So either there are chains like described above at the edges, or there's a chain like that separating two parts of the graph (suppose there was only one route connecting the US to Europe, and it stopped in Newfoundland, Keflavik and Shannon). The last possibility is obviously nonsense, though, we know that major airports are densely connected.
  - saratogacx 2y ago
    It may also depend on optimizations. Potentially you may be able to do fewer hops but if the schedules have 1/week flights they may end up taking 2 weeks calendar time for 7 hops while 20 hops gets you there in 4 days. If the window used for the graph creation doesn't cover enough schedule time, more optimal routes may fall off the edges.
    - dmurray 2y ago
      This doesn't match the phrasing in the presentation, I would expect "the graph has diameter 20" to be defined without any reference to the weights of the edges (whether in flying time, total time, cost...) But it's definitely plausible the author half remembered the routes with 20 hops from some optimized search like this, and wrote the wrong thing in the presentation.
  - cozzyd 2y ago
    Yeah, so far CKX is the airport I can find with the most hops to Anchorage (4, but 3 to Fairbanks which is also fairly well connected). YGZ is likewise 4 hops to Ottawa, and I can't find anything higher in Canada (there are a few that are 4 hops to Montreal in northern Quebec). Nor can I find anything in Greenland more than 4 hops from Copenhagen, Keflavik, or Gatwick (hilariously, that's the fewest-hop big airport for some routes due to flying through Akureyri, which is connected to RKV rather than KEF). There must be some island hopping chain somewhere in the Pacific (or perhaps in the Indian Ocean?) but it's not so easy to find. It seems you're usually a few hops from either Tahiti, Hawaii or Fiji...
- mapt 2y ago
  Has to be worse than that. 20 is still way too many degrees of separation if every region operated on a hub and spoke model. I would imagine we're seeing two to four groupings of sequential routes which are subsidized access. A floatplane which hits every island in the archipelago, like a bus route, before reaching the international airport with jets. Likewise with bush planes in Arctic villages, and regional turboprops that hit a sequence of rural airports because they only attract a few passengers a day on their entire route.

by sho 2y ago

cozzyd 2y ago

I imagine it must be something like small Pacific island to small town in the Canadian far north or something...

bluGill 2y ago
Canada is too rich - there are more likely to be flights.
- cozzyd 2y ago
  Yes probably Russian far north is more likely I guess!
dmurray 2y ago
The next line specifies: > typically this will be a small airport in Alaska or Canada to another small airport in Africa or Indonesia It's still mind blowing to me. Surely any Alaskan airport would be within 5 hops of Anchorage (or not have scheduled flights at all, fine, but that can't be the case here), likewise surely any Indonesian airport is within 5 hops of Jakarta, and Anchorage-Jakarta can certainly be done in 3 hops in a multitude of ways. But one of those assumptions is wrong by 7 hops! There aren't even that many airports to consider, the same presentation gives 4000 as the number included in the analysis. Maybe the graph topology is something like a series of tiny airports that each only connect to the next airport in the series, probably by the same flight that makes multiple stops (not unknown in island hopping, and maybe then in Alaska/Canada too). So you don't really board 20 planes but you do require 20 takeoffs and landings.
- dmurray 2y ago
  Thinking about it, I bet you can prove this is the topology. If the graph is generally densely connected (almost all nodes have 3+ destinations) then the diameter can't be that high compared to the size of the graph. Proof left to the reader. So either there are chains like described above at the edges, or there's a chain like that separating two parts of the graph (suppose there was only one route connecting the US to Europe, and it stopped in Newfoundland, Keflavik and Shannon). The last possibility is obviously nonsense, though, we know that major airports are densely connected.
- saratogacx 2y ago
  It may also depend on optimizations. Potentially you may be able to do fewer hops but if the schedules have 1/week flights they may end up taking 2 weeks calendar time for 7 hops while 20 hops gets you there in 4 days. If the window used for the graph creation doesn't cover enough schedule time, more optimal routes may fall off the edges.
  - dmurray 2y ago
    This doesn't match the phrasing in the presentation, I would expect "the graph has diameter 20" to be defined without any reference to the weights of the edges (whether in flying time, total time, cost...) But it's definitely plausible the author half remembered the routes with 20 hops from some optimized search like this, and wrote the wrong thing in the presentation.
- cozzyd 2y ago
  Yeah, so far CKX is the airport I can find with the most hops to Anchorage (4, but 3 to Fairbanks which is also fairly well connected). YGZ is likewise 4 hops to Ottawa, and I can't find anything higher in Canada (there are a few that are 4 hops to Montreal in northern Quebec). Nor can I find anything in Greenland more than 4 hops from Copenhagen, Keflavik, or Gatwick (hilariously, that's the fewest-hop big airport for some routes due to flying through Akureyri, which is connected to RKV rather than KEF). There must be some island hopping chain somewhere in the Pacific (or perhaps in the Indian Ocean?) but it's not so easy to find. It seems you're usually a few hops from either Tahiti, Hawaii or Fiji...
mapt 2y ago
Has to be worse than that. 20 is still way too many degrees of separation if every region operated on a hub and spoke model. I would imagine we're seeing two to four groupings of sequential routes which are subsidized access. A floatplane which hits every island in the archipelago, like a bus route, before reaching the international airport with jets. Likewise with bush planes in Arctic villages, and regional turboprops that hit a sequence of rural airports because they only attract a few passengers a day on their entire route.