Log-barrier interior point methods are not strongly polynomial

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1

We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for…