Linear Programming (LP) (in 2 minutes)

Overview of Linear Programming in 2 minutes.

----------------------
Additional Information on the distinction between "Polynomial" vs "Strongly Polynomial" algorithms:
An algorithm for solving LPs of the form
max c^t x s.t. Ax \le b
runs in polynomial time if its running time can be bounded by a polynomial D^r, where "r" is some integer, and D is the bit-size of the data of the problem, or in other words, D is the amount of memory that it takes to store the matrix A and the vectors b and c. On the other hand, an algorithm runs in strongly polynomial time if its running time can be bounded by a polynomial n^r m^s, where "r" and "s" are integers, "n" is the number of variables and "m" is the number of constraints.

The distinction is subtle, but is an important one. Essentially, a polynomial time algorithm is allowed to take more time as the size of the coefficients of A grows (while keeping the dimensions of A constant), but a strongly polynomial time algorithm is not.

(I glossed over some details here. For example in the definition of strong polynomial time algorithms, we assume that the basic arithmetic operations take a constant time no matter the size of the operands.)

The interior point method is a polynomial time algorithm, but not a strongly polynomial time one (e.g., arxiv.org/abs/1708.01544).

----------------------
Typos:
"Schedueling" should be "Scheduling"

--------------

Timestamps:
0:00 Motivating Example
0:39 Definition
1:07 Applications
1:42 Code
2:00 Open Problems


---------------
Credit:
🐍 Manim and Python : github.com/3b1b/manim
🐵 Blender3D: www.blender.org/
🗒️ Emacs: www.gnu.org/software/emacs/
Music/Sound: www.bensound.com, Zapsplat.com

This video would not have been possible without the help of Gökçe Dayanık