- A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions Sergei Chubanov (sergei.chubanovuni-siegen.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 non-zero 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 0-1 optimal solutions and the Markov Decision Problem with a fixed discount factor as special cases. We also discuss a class of linear-programming relaxations of 0-1 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/2014Entry Accepted: 12/29/2014Entry Last Modified: 02/01/2015Modify/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 Optimization Online is supported by the Mathematical Optmization Society.