No self-concordant barrier interior point method is strongly polynomial

Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame

It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the…