Short-step Methods Are Not Strongly Polynomial-Time

Manru Zong, Yin Tat Lee, Man-Chung Yue

Short-step methods are an important class of algorithms for solving convex constrained optimization problems. In this short paper, we show that under very mild assumptions on the s…