  


A polynomial projection algorithm for linear programming
Sergei Chubanov(sergei.chubanovunisiegen.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 nonnegativity constraints. Then it uses a procedure that either finds 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 finds a solution in the relative interior of the feasible set. Keywords: Linear programming; polynomial algorithm Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 07/05/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  