Tuesday, June 14, 2005

Khachiyan's ellipsoid method

Tarjan's wonderful book has the following to say (in first chapter) about Khachiyan's ellipsoid method:
  1. It is a very clever n-dimensional generalization of binary search
  2. Khachiyan's method takes approximately the same time for all cases. Simplex algorithm is either very fast, for most cases or very slow for some cases.
  3. Khachiyan's method seems to use very high precision arithmetic, the cost of which the logarithmic cost measure underestimates

No comments: