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 primaldual
algorithms, a primaldual algorithm for shortest paths

Lecture 22 of [2], Chapter 3.4 and 5.4 of [3]

Slides

Video

Lecture 19


A primaldual algorithm for minimum spanning trees  I

Lecture 20, 21 of [2]

Slides

Video

Lecture 20


A primaldual algorithm for minimum spanning trees  II

Lecture 20, 21 of [2]

Slides

Video

Lecture 21


A primaldual 2approximation algorithm for minimum vertex cover

These notes

Slides

Video

Lecture 22


Applications of LP: Zerosum games I (model definition, pure strategies)

Section 8.1 of [1]

Slides

Video

Lecture 23


Applications of LP: Zerosum games II (randomized
strategies, maxmin and minmax)

Section 8.1 of [1]

Slides  Part
1 Slides  Part
2

Video 
Part 1 Video 
Part 2
