## Topological structure and a polynomial-time solution of linear programming over the real numbers. (arXiv:1805.06342v1 [math.OC])

We present an O(mn^2) algorithm for linear programming over the real numbers
with n variables and m problem constraints through deciding the support set a
of the optimal solution. Let z and e be two 2(n+m)-tuples with z representing
the prime, 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 prime
and dual problem constraints, the zero duality gap constraint, but not the
non-negativity constraints, and no limit on the real number t. Let L be the
projection of Z on the hyperplane defined by t = 0. Let Y denote the
(n+m)-subspace where the sum of two components of a point corresponding to a
complementary pair of z equals one, and Q be the sphere in Y centered at e/2 of
a diameter whose square equals 2(n+m). Consider a squeeze mapping involving the
variables of each complementary pair of z. The projection of e on the image of
L of the mapping lies in Q, which is the circumsphere of the hypercube in Y查看全文