Topological structure and a polynomial-time solution of linear programming over the real numbers
From MaRDI portal
Publication:6301655
arXiv1805.06342MaRDI QIDQ6301655FDOQ6301655
Authors: Jingyuan Wei 
Publication date: 16 May 2018
Abstract: We present an O(mn^2) algorithm for linear programming over the real numbers with n primal and m dual variables through deciding the support set a of an optimal solution. Let z and e be two 2(n+m)-tuples with z representing the primal, dual and slack variables of linear programming, and e the all-one vector. Let Z denote the region including all (tz, t) with z meeting the zero duality gap constraint, all primal and dual constraints except for the non-negativity constraints, and without limit on the real number t. Let L be the projection of Z on the hyperplane defined by t = 0. Consider a squeeze mapping involving the two variables of each complementary pair of z. The projection of e on the image of L of the mapping lies in an (n+m-1)-sphere Q centered at e/2 of a diameter whose square equals 2(n+m). The sum of the two components of a complementary pair of z in Q equals one, and Q is the circumsphere of the hypercube where each component of its vertices takes value in {0, 1}. One vertex v* called the solution vertex is the indicator vector of a. The algorithm uses squeeze mapping to move the aforementioned projection around v* along Q so that a is identified at certain position. It consists of O(n) unidimensional squeeze mappings, each of which uses O(mn) arithmetic operations.
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
This page was built for publication: Topological structure and a polynomial-time solution of linear programming over the real numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301655)
