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., [ Ссылка ]).
----------------------
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 : [ Ссылка ]
🐵 Blender3D: [ Ссылка ]
🗒️ Emacs: [ Ссылка ]
Music/Sound: www.bensound.com, Zapsplat.com
This video would not have been possible without the help of Gökçe Dayanıklı.
