The algorithm proposed in this paper runs in a polynomial oracle time, i.e., in a number of arithmetic operations and calls to the separation oracle bounded by a polynomial in the number of variables and in the maximum binary size of an entry of the coefficient matrix. This algorithm is much simpler than traditional polynomial algorithms such as the ellipsoid method and the volumetric barrier method. In particular, we do not need the notion of volume to prove the polynomial complexity of our algorithm.
Article
View A polynomial algorithm for linear feasibility problems given by separation oracles