Abstract
Since the 1970's, one of the most intriguing research question in linear optimization (LO) has been the the following: is there an algorithm which solves
any LO problem in polynomiM (or strongly polynomiM) number of iteration, i.e.,
the complexity of the algorithm is O(p(n, L)) (or O(p(~))), where p is a polynomial of finite degree, n is the number of variables and L is the input size of the LO problem.
any LO problem in polynomiM (or strongly polynomiM) number of iteration, i.e.,
the complexity of the algorithm is O(p(n, L)) (or O(p(~))), where p is a polynomial of finite degree, n is the number of variables and L is the input size of the LO problem.
Original language | English |
---|---|
Pages (from-to) | 277-281 |
Number of pages | 5 |
Journal | TOP: Transactions in Operations Research |
Volume | 12 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Dec 2004 |
Keywords
- linear optimization
- IPMs
- polynomial
- algorithm