Monthly Archives: April 2014

04/25/2014
Algorithmic Trends

Two new homework sets

The two new homework sets Homework 4 and Homework 5 are due on 15.05.2014.

04/23/2014
Algorithmic Trends

The last two lectures.

The lecture on flows in planar graph is below it contains ideas from [1,2,3].

The lecture on mechanism design.

[1] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Improved algorithms for min cut and max flow in undirected planar graphs. STOC 2011: 313-322.
[2] Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen: Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. FOCS 2010: 601-610.
[3] Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Single Source – All Sinks Max Flows in Planar Digraphs. FOCS 2012: 599-608.

04/09/2014
Algorithmic Trends

Algorithmic Trends: Third Homework

The third homework is due on the 23rd of April.