Optimization Online


A polynomial algorithm for linear feasibility problems given by separation oracles

Sergei Chubanov (sergei.chubanov***at***uni-siegen.de)

Abstract: 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.

Keywords: linear programming, convex optimization

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 01/27/2017
Entry Accepted: 01/27/2017
Entry Last Modified: 03/23/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society