##
How partial knowledge helps to solve linear programs

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