Routing and AI algorthmic efficiency

From: Dan Clemmensen (
Date: Mon Feb 11 2002 - 17:58:12 MST

I mentioned that the best routing algorithms, when compared to primitive
routing algorithms, can at best double the utilization of a large data
network. A shy lurker e-mailed me privately and asked if there is an
analogy with other algorithms, and in particular with AI algorithms. I
think that this is a good question.

Basically, to a first approximation, you can get the same performance
by over-engineering a data network by a factor of two as you can get
with the most clever routing algorithm (in practice, not in theory.)

This leads to two questions:
   1) Is any part of the AI problem isomorphic to the routing problem?
   2) What parts of the AI problem, if any, are amenable to brute-force
over-engineering, and what is a good guesstimate of the "cleverness
factor" of a clever algorithm versus a brute-force algorithm? The
cleverness factor for routing is a simple factor of 2.

As an aside, I mentioned to our "shy lurker" that this is exactly the
kind of question we like to see posted onto the list. I hope our lurker
will begin posting.

This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 13:37:38 MST