5 ms·

Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algo

by ubj 3y ago

Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.

dang 3y ago
I think we fixed that, albeit by accident when I edited the title earlier. If it needs further fixing let me know!
eru 3y ago
You are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful. Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough. (And many integer linear programming solvers are based on continuous linear programming solvers.)
- ubj 3y ago
  True, these are all fair points! I didn't intend to diminish the impact or complexity of linear programming solvers. Well-written solvers are some of the most useful and powerful computational tools that exist today.
  - eru 3y ago
    Definitely. Advances in numerics in general, matrix multiplication in particular, and solving of systems of (continuous) linear equation and continuous linear programming are to computing what advances in basic material science are to engineering. Modern concrete and steel (and plastics etc) allow you to build so much more advanced, but also simpler, than the kinds of wacky shenanigans people had to pull off in eg the 19th century just to get high pressure steam engines to work (if they could do that at all).
- isaacfung 3y ago
  Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study the worst case complexity of algorithms when the inputs are randomly perturbed by a small amount. https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf
  - pfdietz 3y ago
    Spielman in 2013 also (with Adam Marcus and Nikhil Srivastava) came out of left field and solved the long open Kadison-Singer problem, to the surprise of more mainstream mathematicians. I find this interplay between "traditional" mathematicians and those in allied fields like CS to be very interesting.

by ubj 3y ago

dang 3y ago

I think we fixed that, albeit by accident when I edited the title earlier. If it needs further fixing let me know!

eru 3y ago

You are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful. Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough. (And many integer linear programming solvers are based on continuous linear programming solvers.)

ubj 3y ago
True, these are all fair points! I didn't intend to diminish the impact or complexity of linear programming solvers. Well-written solvers are some of the most useful and powerful computational tools that exist today.
- eru 3y ago
  Definitely. Advances in numerics in general, matrix multiplication in particular, and solving of systems of (continuous) linear equation and continuous linear programming are to computing what advances in basic material science are to engineering. Modern concrete and steel (and plastics etc) allow you to build so much more advanced, but also simpler, than the kinds of wacky shenanigans people had to pull off in eg the 19th century just to get high pressure steam engines to work (if they could do that at all).
isaacfung 3y ago
Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study the worst case complexity of algorithms when the inputs are randomly perturbed by a small amount. https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf
- pfdietz 3y ago
  Spielman in 2013 also (with Adam Marcus and Nikhil Srivastava) came out of left field and solved the long open Kadison-Singer problem, to the surprise of more mainstream mathematicians. I find this interplay between "traditional" mathematicians and those in allied fields like CS to be very interesting.