Please, find 3 volumes by Alexander Schrijver : Combinatorial Optimization. Polyhedra and Efficiency .http://www.amazon.com/Combinatorial-Optimization-Efficiency-Alexander-Schrijver/dp/B00866D0LQ/ref=sr_1_cc_2?s=aps&ie=UTF8&qid=1446407503&sr=1-2-catcorr&keywords=combinatorial+optimization.+polyhedra+and I hope, this information will help you a lot
In short the best methods complexity-wise are interior-point algorithms, the best of which has a complexity of a constant times something like the number of variables to the power of 3.5. This "constant" however is a function of the size of the input data, so in complexity words we would say that we do not yet know if there is an algorithm for LP that is strongly polynomial (a polynomial that does not depend on the input data).
So there's a nice project for a good PhD student! :-)
Tnx for all the answers.
I would like to know the complexity of linear programming in function of the number of variables.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics