Combinatorial algorithms for Linear Programming
 

In this mini course I plan to algorithms for special classes of Linear programming problems that are of a combinatorial nature and have better running times than the generic LP algorithms. Some of the papers that we would be discussing/referrring to in this mini course are

Potential function methods for approximately solving linear programmimg problems: Theory and Practice
This is a nice survey by Dan Bienstock from April 2001

Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities

Garg and Koenemann: Faster and Simpler algorithms for multicommodity flow and other fractional packing problems.

Grigoriadis and Khachiyan: Fast approximation schemes for convex programs with many block and coupling constraints

Plotkin, Shmoys and Tardos: Fast approximation algorithms for fractional packing and covering problems.

Young: Sequential and parallel algorithms for mixed packing and covering.

Garg and Khandekar: Fast Approximation algorithms for steiner forest and related problems