[Colloq] Monday Sept 28th -- Speaker: Vijay V. Vazirani -- MIT Applied Math Colloquium -- 4:30 PM

[Rachel Kalweit]

APPLIED MATHEMATICS COLLOQUIUM

Monday September 28th 2009

Time: 4:30 PM

Location: MIT, Building 4, Room 370
Refreshments are available in Building 2, Room 290
(Math Common Room) between 3:30 – 4:30 PM

Speaker: Vijay V. Vazirani (Georgia Tech)

Title: Combinatorial Algorithms for Convex Programs (Capturing Market 
Equilibria and Nash Bargaining Solutions)

Abstract:
Over the last 50 years, the primal-dual paradigm has had two highly 
successful “lives”-- in combinatorial optimization and in approximation 
algorithms. In addition to yielding efficient and practically useful 
algorithms, it has also provided deep insights into the combinatorial 
structure underlying the problems solved.

Recently, in the context of solution of problems from game theory and 
mathematical economics, a third life of this paradigm appears to be 
emerging: combinatorial algorithms for solving certain classes of convex 
programs. The algorithms found so far are based on exploiting a 
surprisingly rich and clean structure, which is in some ways reminiscent 
of the majestic structure of matching.

Besides providing an in-depth perspective on this new development, I 
will introduce the fascinating problems that led to it and point out the 
challenges that lie ahead.

This talk is based on Chapter 5 from 
http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf 
and http://www.cc.gatech.edu/fac/Vijay.Vazirani/NBalg.pdf

******
Applied Math Colloquium Website: http://math.mit.edu/amc/fall09/
Applied Math Colloquium poster: 
http://math.mit.edu/amc/fall09/Vijay_Vazirani.pdf

Massachusetts Institute of Technology
Department of Mathematics
Cambridge, MA 02139
http://math.mit.edu

******