ISSN:
1432-5217
Keywords:
Ellipsoid method
;
linear programming
;
simplex
;
volume
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01199467
Permalink
