Why is the interior points method for linear programs polynomially bounded if it only produces a solution with epsilonaccuracy? asked 24 Dec '14, 19:29 zBirdy 
Polynomial complexity of algorithms that approximate the solution to arbitrary accuracy include the accuracy parameter as an argument to the polynomial. If the parameter is itself related to the size of the input, then that relation can be incorporated into the others. Thus, in the case of an interiorpoint LP algorithm, if \(\epsilon \leq 2^{2L}\) then the final solution can be rounded to an exact solution in \(O(n^3)\) time. A solution with that tolerance can be reached in \(O(\sqrt{n}L)\) iterations, so the overall complexity is \(O(n^3L)\). Here (PDF) is a nice set of slides from Florian Potra (where I pulled the above result). answered 25 Dec '14, 11:28 Matthew Salt... ♦ thank you for you answer. and to get the first starting point it uses the phase I problem (like the simplex method) and solves this in polynominal time and then the real problem again in polynominal time?
(25 Dec '14, 15:06)
zBirdy
There are various techniques, but one of the more common ones starts infeasible and takes steps composed of components that improve feasibility, optimality, and moving to the analytic center of the feasible region simultaneously, adjusting the relative weights between the component directions as the algorithm progresses. Potra's slides suggest that determining infeasibility might require some more iterations, but still polynomial.
(25 Dec '14, 16:00)
Matthew Salt... ♦

related
I'm not wellversed in the details, but I keep reading about some "clever rounding techniques."