Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
This paper studies the boundary behavior of some interior point algorithms for linear programming. The algorithms considered are Karmarkar's projective rescaling algorithm, the linear rescaling algorithm which was proposed as a variation on Karmarkar's algorithm, and the logarithmic barrier technique. The study includes both the continuous trajetories of the vector fields induced by these algorithms and also the discrete orbits. It is shown that, although the algorithms are defined on the interior of the feasible polyhedron, they actually determine differentiable vector fields on the closed polyhedron. Conditions are given under which a vector field gives rise to trajectories that each visit the neighborhoods of all the vertices of the Klee-Minty cube. The linear rescaling algorithm satisfies these conditions.
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004