# interior points method polynominal time

 2 Why is the interior points method for linear programs polynomially bounded if it only produces a solution with epsilon-accuracy? asked 24 Dec '14, 19:29 zBirdy 171●2●12 accept rate: 20% related (24 Dec '14, 20:52) Austin Buchanan I'm not well-versed in the details, but I keep reading about some "clever rounding techniques." (24 Dec '14, 20:58) Austin Buchanan

 4 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 interior-point 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... ♦ 4.7k●3●10 accept rate: 17% 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... ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: