Une série de conférences / A series of lectures
Le lundi 11 septembre 2006 / Monday, September 11, 2006
16 h / 4:00 p.m.
Université de Montréal
2920, ch. de la Tour
Salle / Room 1140
Cette conference s'adresse à un large auditoire.
Suitable for a general audience.
Approximation algorithms and Grothendieck type inequalities
I will describe a connection between a classical inequality of Grothendieck and approximation algorithms based on semidefinite programming.
The investigation of this connection suggests the definition of a new graph parameter, called the Grothendieck constant of a graph, whose study is motivated by algorithmic applications and leads to several extensions of the inequality of Grothendieck, to an improvement of a recent result of Kashin and Szarek, and to a solution of a problem of Megretski and of Charikar and Wirth.
The lecture will include a description of Grothendieck's Inequality, its extensions, and their relevance to approximation algorithms. The new material is based on three recent papers with various subsets of A. Naor, E. Berger, K. Makarychev, and Y. Makarychev.
Une réception suivra la conférence au Salon Maurice-L'Abbé, Pavillon André-Aisenstadt (Salle 6245).
There will be a reception after the lecture in Salon Maurice-L'Abbé, Pavillon André-Aisenstadt (Room 6245).