Re: Bidirectional Binary Self-Joins

Martha Stewart called it a Good Thing when paul c <toledobythesea_at_oohay.ac> wrote:
> Anne & Lynn Wheeler wrote:
> ...
>> so one of the "ten impossible" things (current ROUTES couldn't do and
>> we were suppose to implement), was being able to find connections
>> between any two airports (some 4k plus) in the world. for demo, they
>> would give two airports codes ... frequently ones that nobody had ever
>> heard of before on opposite sides of the world. there were some that
>> took more than 24hrs elapsed time with 5-6 different connections.
>> ...
>
> I knew one consulting company that charged an airline a lot of money
> to do that. Eventually the effort was stopped when both parties were
> asked to solve the "travelling salesman" problem in a most general
> way, which was more or less what they were trying to do. The problem
> was new to both parties, even to the airline's most experienced
> business analysts! What's more, since that airline did a lot of
> contracting out to other airlines, they wanted to include all airports
> known to IATA, which numbered about 6,000 airports at the time.
>
> The segment combinations that involved factorials also got the
> consulting companies quite interested, suggesting schemas of hundreds
> of tables for routing alone, let alone all the other stuff an airline
> has to account for today.

Which is pretty dumb when Dijkstra's algorithm is actually pretty good for solving the subproblems.

What's surprising is that there are now getting to be pretty decent approximate TSP solutions...

-- 
let name="cbbrowne" and tld="acm.org" in String.concat "_at_" [name;tld];;
http://linuxdatabases.info/info/
"Wrongs are often forgiven, but contempt never is. Our pride remembers
it forever." -- Lord Chesterfield,