Linear programming in O((n3/ln n)L) operations

Kurt M. Anstreicher
Additional contact information
Kurt M. Anstreicher: Department of Management Sciences, University of Iowa

No 1997046, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We show that the complexity to solve linear programming problems, using standard linear algebra, can be reduced to O([n3/lnn]L) operations, where n is the number of variables in a standard form problem with integer data of bit size L. Our technique combines partial updating with a preconditioned conjugate gradient method, in a scheme first suggested by Nesterov and Nemirovskii.

Date: 1997-06-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1997.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1997046

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().