Linear Programming (LP) (in 2 minutes) скачать в хорошем качестве

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., https://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 : https://github.com/3b1b/manim 🐵 Blender3D: https://www.blender.org/ 🗒️ Emacs: https://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ıklı.