Large 00016

Matroidal Approaches for Approximation Algorithms

Michel Goemans

Recorded 12 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


Matroids are powerful combinatorial structures that allow to model many combinatorial optimization problems exactly. Using them to design and analyze approximation algorithms for hard combinatorial optimization problems appears very promising but also very challenging.

In this talk, after describing some of the important features of matroids for optimization purposes, I will discuss some of its applications to the design and analysis of approximation algorithms.

Watched 7050 times.