MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Question - Karmarkar's Algorithm

  • To: mathgroup at
  • Subject: [mg33719] Question - Karmarkar's Algorithm
  • From: Mark Van Noy <mvannoy at>
  • Date: Mon, 8 Apr 2002 03:05:06 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

I am working on an AI project and have been looking for a computer 
application of "Karmarkar's Algorithm."  I had half expected that 
Mathematica would contain this application.  However, the information on 
Wolfram's website doesn't mention it.  Is there an available application 
of Mathematica that implements Karmarkar's Algorithm?

Mr. Karmarkar's algorithm was highlighted in a scientific publication 
around 1989.  At that time it was very new.  The story is basically 
this:  Mr. Karmarkar is (was?) a mathematician working for AT&T (Bell 
Labs?).  He came up with an optimization algorithm that far exceeds the 
ability of linear algebra.  Its advantage is that it can work with a 
very large number of variables and still quickly calculate an accurate 
solution, using a reasonable amount of computing power.  The "secret" of 
the algorithm is that it uses vectors.  AT&T's application was/is rapid 
optimization of phone call routing during heavy calling periods.  
Another obvious application is 'real-time' scheduling of airline 
equipment, crews, gates, times, and routes.  The ability to do this on 
the fly (so to speak), using desktop computing rather than mainframes, 
has significant implications.

According to the article, AT&T would not let Mr. Karmarkar discuss it or 
publish his findings, due to obvious commercial considerations.  When 
AT&T had completed implementation, they allowed him to present them in a 
professional forum.  After he made his presentation, there was 
discussion of whether it actually worked, and some challenged his 
assertions.  In defense of his professional standing, Mr. Karmarkar 
found it necessary to meet with doubters on an individual basis to 
explain his algorithm.

Right now, this project is wholly my personal creation (i.e., I am not 
doing this for a company, as part of my job or something), so it's slow 
work.  I am developing an AI concept based on the machine-formation of 
"opinions" from assimilation and correlation of real-time raw data 
streams and existing opinions.  The idea is to correlate data to form 
symbols, associate knowledge and opinions with those symbols, and enable 
formation of layers of opinions through integration.  I have a construct 
of opinions as vectors and need a computer application that rapidly 
considers a vast array of loosely associated opinions and either selects 
existing opinions, or forms new opinions, upon which to base selection 
and execution of a set of "learned" output sequences that become 
real-time response (e.g., conversational robotic speech).  I believe Mr. 
Karmarkar's algorithm holds promise.

OK, that's the basic situation.  If anyone has useful information about 
this admittedly esoteric application, I would appreciate it if they 
could provide a helping hand.

Mark Van Noy

  • Prev by Date: Re: Re: Automatic restart
  • Next by Date: Re: Optional
  • Previous by thread: Re: [Q] : huge number, ciphers after decimal point?
  • Next by thread: Question - Karmarkar's Algorithm