On the worst case complexity of potential reduction algorithms for linear programming
Bertsimas, Dimitris
Xiaodong, Luo

Data: 1997
Resum: There are several classes of interior point algorithms that solve linear programming problems in O(V~nL) iterations. Among them, several potential reduction algorithms combine both theoretical (O(V~nL) 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(V~nL) 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 (Omega) (V~nL) iterations to find an optimal solution. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Interior point methods ; Lower bounds on complexity ; Potential reduction algorithms
Publicat a: Mathematical Programming, vol. 77 n. 3 (1997) p. 321-333, ISSN 0025-5610

13 p, 551.2 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir