There are several classes of interior point algorithms that solve linear programming problems in O(√(n)L) iterations. Among them, several potential reduction algorithms combine both theoretical (O(√(n)L) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(√(n)L) is tight for several potential reduction algorithms, i.e. there is a class of examples with network structure, in which the algorithms need at least Ω(√(n)L) iterations to find an optimal solution.
