Optimization Online


A polynomial projection algorithm for linear programming

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

Abstract: We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either fi nds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the homogeneous system so that its feasible solutions in the unit cube get closer to the vector of all ones. In a polynomial number of calls to the procedure the algorithm either proves that the original system is infeasible or fi nds a solution in the relative interior of the feasible set.

Keywords: Linear programming; polynomial algorithm

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


Download: [PDF]

Entry Submitted: 07/05/2013
Entry Accepted: 07/06/2013
Entry Last Modified: 07/05/2013

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