Simplices by point-sliding and the Yamnitsky-Levin algorithm

Share/Save/Bookmark

Faigle, U. and Hunting, M. and Kern, W. and Prakash, R. and Supowit, K.J. (1997) Simplices by point-sliding and the Yamnitsky-Levin algorithm. Mathematical methods of operations research, 46 (1). pp. 131-142. ISSN 1432-2994

[img]PDF
Restricted to UT campus only
: Request a copy
427Kb
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¦aTx ≤ β}, the algorithm finds a simplexSYL of small volume that enclosesS ∩ {x¦aTx ≤ β}. We interpretSYL 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.
Item Type:Article
Copyright:© 1997 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/71486
Official URL:http://dx.doi.org/10.1007/BF01199467
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140783