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's gravatar image

accept rate: 20%

(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

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%20Saltzman's gravatar image

Matthew Salt... ♦
accept rate: 17%

edited 25 Dec '14, 11:38

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... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 24 Dec '14, 19:29

Seen: 582 times

Last updated: 25 Dec '14, 16:00

OR-Exchange! Your site for questions, answers, and announcements about operations research.