Mathematical Programming and Polyhedral Combinatorics

Petr Kolman, Martin Loebl

In 2016/17, lectures take place every week on Friday from 9 am in S3.

Lecture notes on polynomial time LP algorithms by P. Kolman (in Czech)
Lecture notes on the ellipsoid algorithm by M. Goemans
Lecture notes on interior point method by M. Goemans (see chapter 13)
Textbook Linear Programming by Howard Karloff, chapters 4 and 5 - available in the University library at Mala Strana.

Covered topics

• October 7, Martin Loebl
  • Introduction to matroids: basic definition, graphic matroids, matroids from a matrix, independent sets, bases, rank. Submodularity.
• October 14, Martin Loebl
  • Graphic matroids are representable over any field. A combinatorial representation of simple matroids of rank 3.
• October 21, Martin Loebl
  • Greedy algorithm, convex hull of independent sets of a matroid.
• October 28 - no lectures, public holiday
• November 4, Martin Loebl
  • Dual matroid, contraction, deletion, intersection of 2 matroids.
• November 11, Petr Kolman
  • Introduction to polynomial time algorithms for linear programming.
• November 18, Martin Loebl
  • Duality of planar graphs and matroid duality, max cut problem for planar graphs, without proofs: mac cut is polynomial on any fixed surface (duality of enumeration).
• November 25, Martin Loebl
  • Submodular functions: examples, marginal values, polymatroids and extended polymatroids, min of submodular function, maximization of a monotone submodular function with matroid constraints and on-line auctions.
• December 2, Petr Kolman
  • Ellipsoid algorithm, part I (How to start, Iterative step in the simple case).
• December 9, Petr Kolman
  • Ellipsoid algorithm, part II (Iterative step in the general case, When to stop).
• December 16, Petr Kolman
  • Ellipsoid algorithm, part III (How to get rid of the simplifying assumptions).
  • Interior-point Methods, part I (Potential function, structure of the algorithm).
• January 6, 2017, Petr Kolman
  • Interior-point Methods, part II (Iterative step in the simple case).
• January 13, 2017, Petr Kolman
  • Interior-point Methods, part III (Iterative step in the general case, Initial Step, Final Step [sketch]).

Other courses on Combinatorial Optimization

• Combinatorial Optimization by Michel Goemans at MIT
• Linear and Semidefinite Programming by Anupam Gupta and Ryan O'Donnell at CMU