|
Lecture 1
|
13.04.2021
|
Linear Programming problem, Examples
|
Chapters 1 and 2 of [1]
|
Slides
|
Video
|
|
Lecture 2
|
17.04.2021
|
Solving LPs in 2 dimensions; Integer Linear Programs; LP relaxation; Maximum weight matching
|
Chapters 1 and 3 of [1]
|
Slides
|
Video
|
|
Lecture 3
|
20.04.2021
|
ILP Vs LP relaxation: Minimum vertex cover, Maximum
independent set
|
Chapter 3 of [1]
|
Slides
|
Video
|
|
Lecture 4
|
04.05.2021
|
Equational form; Some linear algebra basics
|
Chapter 4.1 of [1]
Lecture 3 of [2]
|
Slides
|
Video
|
|
Lecture 5
|
06.05.2021
|
Dimension of the nullspace of A in terms of row rank and
column rank
|
Lectures 4 and 6 of [2]
|
Slides
|
Video
|
|
Lecture 6
|
11.05.2021
|
Basic feasible solutions
|
Chapter 4.2 of [1]
|
Slides
|
Video
|
|
Lecture 7
|
13.05.2021
|
Discussion of Problem Sheets 1 and 2
|
|
Slides
|
Video
|
|
Lecture 8
|
18.05.2021
|
Convex polyhedra, vertices, extreme points and basic
feasible solutions
|
Chapter 4.3 and 4.4 of [1]
Lectures 7, 8, 9 of [2]
|
Slides
|
Video
|
|
Lecture 9
|
20.05.2021
|
The Simplex method
|
Chapter 5.1, 5.2 and 5.3 of [1]
|
Slides
|
Video
|
|
Lecture 10
|
22.05.2021
|
The Simplex method - finding initial feasible basis, formalization
|
Chapter 5.4, 5.5 and 5.6 of [1]
|
Slides
|
Video
|
|
Lecture 11
|
25.05.2021
|
The Simplex method - proof of termination when Bland's
pivoting rule is used
|
Chapter 5.7, 5.8 of [1]
|
Slides
|
Video
|
|
Lecture 12
|
27.05.2021
|
Dual of an LP, Weak duality theorem
|
Chapter 6.1, 6.2 of [1]
|
Slides
|
Video
|
|
Lecture 13
|
01.06.2021
|
Proof of duality using Simplex
|
Chapter 6.3 of [1]
|
Slides
|
Video
|
|
Lecture 14
|
03.06.2021
|
Discussion of Problem Set 3
|
|
Slides
|
Video
|
|
Lecture 15
|
08.06.2021
|
Some clarifications about bfs and extreme points
|
|
Slides
|
Video
|
|
Lecture 16
|
10.06.2021
|
Geometric interpretation of duality
|
|
Slides
|
Video
|
|
Lecture 17
|
15.06.2021
|
Complementary Slackness
|
Lecture 15 from [2]
|
Slides
|
Video
|
|
Lecture 18
|
|
Combinatorial optimization, introduction to primal-dual
algorithms, a primal-dual algorithm for shortest paths
|
Lecture 22 of [2], Chapter 3.4 and 5.4 of [3]
|
Slides
|
Video
|
|
Lecture 19
|
|
A primal-dual algorithm for minimum spanning trees - I
|
Lecture 20, 21 of [2]
|
Slides
|
Video
|
|
Lecture 20
|
|
A primal-dual algorithm for minimum spanning trees - II
|
Lecture 20, 21 of [2]
|
Slides
|
Video
|
|
Lecture 21
|
|
A primal-dual 2-approximation algorithm for minimum vertex cover
|
These notes
|
Slides
|
Video
|
|
Lecture 22
|
|
Applications of LP: Zero-sum games I (model definition, pure strategies)
|
Section 8.1 of [1]
|
Slides
|
Video
|
|
Lecture 23
|
|
Applications of LP: Zero-sum games II (randomized
strategies, maxmin and minmax)
|
Section 8.1 of [1]
|
Slides - Part
1 Slides - Part
2
|
Video -
Part 1 Video -
Part 2
|