Some experimental results on placement techniques
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
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.
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev