ON THE WORST-CASE COMPLEXITY OF POTENTIAL REDUCTION ALGORITHMS FOR LINEAR-PROGRAMMING

There are several classes of interior point algorithms that solve line ar programming problems in O(root L) iterations, Among them, several p otential reduction algorithms combine both theoretical (O(root L) iter ations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical im plementations. It is a significant open question whether interior poin t algorithms can lead to better complexity bounds. In the present pape r we give some negative answers to this question for the class of pote ntial reduction algorithms. We show that, even if we allow line search es in the potential function, and even for problems that have network structure, the bound O(root nL) is tight for several potential reducti on algorithms, i.e., there is a class of examples with network structu re, in which the algorithms need at least Omega(root nL) iterations to find an optimal solution. (C) 1997 The Mathematical Programming Socie ty, Inc.