## How partial knowledge helps to solve linear programs

### Yinyu Ye

We present results on how partial knowledge helps to solve linear programs. In particular, if a linear inequality system, \$A\x=\b\$ and \$\x\ge 0\$, is known to have an interior feasible point, then we show that finding a feasible point to this system can be done in \$O(n^{2.5}c(A))\$ iterations by the layered interior-point method, and each iteration solves a least-squares problem, where \$n\$ is the dimension of vector \$\x\$ and \$c(A)\$ is the condition number of matrix \$A\$ defined in \cite{VavasisYe}. This complexity bound is reduced by a factor \$n\$ from that when no such knowledge exists.

Contact: yyye@dollar.biz.uiowa.edu