- It is a very clever n-dimensional generalization of binary search
- 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.
- Khachiyan's method seems to use very high precision arithmetic, the cost of which the logarithmic cost measure underestimates
Tuesday, June 14, 2005
Tarjan's wonderful book has the following to say (in first chapter) about Khachiyan's ellipsoid method:
Posted by ramakrishna u at 6/14/2005 02:45:00 PM