Fall 2017

Discrepancy and Approximation Algorithms

Monday, Sep. 11, 2017 2:00 pm3:00 pm

Add to Calendar

Combinatorial discrepancy has recently found applications in approximation algorithms, and, in particular, in designing new LP rounding algorithms. It can be seen as a common generalization to randomized and iterated rounding, as well as to total unimodularity. In this talk we will give an introduction to combinatorial discrepancy, focusing on the discrepancy of matrices, and its connections to LP rounding. We will describe several beautiful discrepancy minimization algorithms based on geometric random walks. Finally, we will also touch on approximation algorithms for discrepancy itself.