  


A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions
Sergei Chubanov (sergei.chubanovunisiegen.de) Abstract: This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each nonzero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of the number of variables. We do not impose any additional restrictions on $c$ and $A.$ This class of problems includes linear optimization problems having 01 optimal solutions and the Markov Decision Problem with a fixed discount factor as special cases. We also discuss a class of linearprogramming relaxations of 01 integer problems that can be solved in strongly polynomial time by our algorithm. Keywords: Linear programming, polynomial algorithm, strongly polynomial algorithm. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 12/28/2014 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  