Abstract
Yamnitsky and Levin proposed a variant of Khachiyan's ellopsoid method for testing feasibility of systems of linear inequalities that also runs in polynomial time but uses simplices instead of ellipsoids. Starting with then-simplexS and the half-space {x¦a Tx ≤ β}, the algorithm finds a simplexS YL of small volume that enclosesS ∩ {x¦a Tx ≤ β}. We interpretS YL as a simplex obtainable by point-sliding and show that the smallest such simplex can be determined by minimizing a simple strictly convex function. We furthermore discuss some numerical results. The results suggest that the number of iterations used by our method may be considerably less than that of the standard ellipsoid method.
Similar content being viewed by others
References
Akgül M (1984) Topics in relaxation and ellipsoidal methods. Pitman, Boston, Research Notes in Mathematics 97
Bartels SG (1995) A second look at Yamnitsky and Levin's simplex algorithm. Preprint, FB Mathematik, Technische Universiät Berlin
Bland RG, Goldfarb D, Todd MJ (1981) The ellipsoid method: A survey. Operations Research 29:1039–1091
Chvátal V (1983) Linear programming. W. H. Freeman, New York
Ecker JG, Kupferschmid M (1985) A computational comparison of the ellipsoid algorithm with several nonlinear programming algorithm. SIAM Journal on Control and Optimization 23: 657–674
Faigle U, Hunting M, Kern W (1996) On a variant of the ellipsoid method: Using simplices instead of ellipsoids, extended abstract. In: Kleinschmidt P et al. (eds) Operations Research Proceedings 1995, Springer-Verlag, Berlin: 1–6
Frenk JBG, Gromicho J, Zhang S (1994) A deep cut ellipsoid algorithm for convex programming: Theory and applications. Mathematical Programming 63:83–108
Gács P, Lovász L (1981) Khachiyan's algorithm for linear programming. Mathematical Programming Study 14:61–68
Goldfarb D, Todd MJ (1982) Modifications and implementation of the ellipsoid algorithm for linear programming. Mathematical Programming 23:1–19
Khachiyan LG (1979) A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20:191–194
Prakash R, Supowit KJ (1991) Increasing the rate of convergence of Yamnitsky and Levin's algorithm. Working Paper
Schrijver A (1986) Theory of linear and integer programming. Chichester
Yamnitsky B, Levin LA (1982) An old linear programming problem runs in polynomial time. In: IEEE Symposium on the Foundations of Computer Science: 327–328
Zorychta K (1982) Improvements of the ellipsoidal algorithm for linear inequalities. Bull. Acad. Polon. Sci. Sér. Sci. Math. 30:97–103
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Faigle, U., Hunting, M., Kern, W. et al. Simplices by point-sliding and the Yamnitsky-Levin algorithm. Mathematical Methods of Operations Research 46, 131–142 (1997). https://doi.org/10.1007/BF01199467
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01199467