## A Fast Polynomial-time Primal-Dual Projection Algorithm for Linear Programming. (arXiv:1810.04517v1 [math.OC])

Traditionally, there are several polynomial algorithms for linear programming
including the ellipsoid method, the interior point method and other variants.
Recently, Chubanov [Chubanov, 2015] proposed a projection and rescaling
algorithm, which has become a potentially \emph{practical} class of polynomial
algorithms for linear feasibility problems and also for the general linear
programming. However, the Chubanov-type algorithms usually perform much better
on the infeasible instances than on the feasible instances in practice. To
explain this phenomenon, we derive a new theoretical complexity bound for the
infeasible instances based on the condition number, which shows that algorithms
can indeed run much faster on infeasible instances in certain situations. In
order to speed up the feasible instances, we propose a \emph{Polynomial-time
Primal-Dual Projection} algorithm (called PPDP) by explicitly developing the
dual algorithm. The numerical results validate that our PPDP algorithm achi查看全文