
Matroidal Approaches for Approximation Algorithms
Michel Goemans
Recorded 12 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
Abstract
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 1024 times.
Watch