Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?

  • $\begingroup$ What research have you done? Have you read the Wikipedia article, for instance? It describes some of the history and some ways that theoretical advices in linear programming had practical impact -- see, e.g., interior point methods, which are useful in practice. We expect you to do a significant amount of research before asking and to show us in the question what research you've done. If you give us more to work with, that makes it easier to provide you a useful answer at the right level of detail and sophistication. $\endgroup$ – D.W. Feb 13 '15 at 23:43
  • $\begingroup$ @D.W. Wikipedia hints that we care since we'd like a polytime algorithm for the real RAM, but it's not clear whether this is practically important – floating point reals are not the same as the reals in the real RAM model. $\endgroup$ – Yuval Filmus Feb 14 '15 at 1:21
  • $\begingroup$ @YuvalFilmus, understood. I was thinking of a broader argument: theoretical advances in the past (showing that LP can be solved in polynomial time) have have had a practical impact (namely, interior point methods), so there could be a practical improvement -- though of course everything I'm saying is speculation. $\endgroup$ – D.W. Feb 14 '15 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.