Information for lecture "Mathematical Programming and Polyhedral Combinatorics"

Tutorials: YOU DECIDE WHAT YOU WANT, from: (1) reading on algorithmic game theory, contact Martin Loebl or (2) LP solvers practise, contact Petr Kolman.

We start teaching remotely by ZOOM: Meeting ID: 955 6235 6788 Passcode: 978732

From November 23 the lecture is given by Petr Kolman, see https://kam.mff.cuni.cz/~kolman/matprog.html

October 5: Introduction to matroids: basic definition, graphic matroids, matroids from a matrix, independent sets, bases, rank. Submodularity.

Lecture notes Matroidy1

Lecure slides Matroidy05102020

The video is available at https://kam.mff.cuni.cz/~loebl/video/zoom_0.mp4

October 12: Duality and planarity, minors, representable matroids.

Lecture notes Matroidy2

Lecure slides Matroidy12102020

The video is available at https://kam.mff.cuni.cz/~loebl/video/zoom_1.mp4

October 19: intersection and union of matroids, minmax theorems, greedy algorithm.

Lecture notes Matroidy1, Matroidy2

Lecure slides Matroidy19102020

October 26: Submodular functions introduction

Lecure slides Matroidy26102020

The video is available at https://kam.mff.cuni.cz/~loebl/video/zoom_2.mp4

November 02: Submodular functions: polymatroids and minimization

Lecure slides Matroidy02112020

The video is available at https://kam.mff.cuni.cz/~loebl/video/zoom_3.mp4

November 09: Algorithmic Game Theory: basic examples

Lecure slides Matroidy09112020

The video is available at https://kam.mff.cuni.cz/~loebl/video/zoom_5.mp4

November 16: Algorithmic Game Theory: markets and prices