Wednesday, September 22, 2010 4:00 pm
-
Thursday, September 23, 2010 4:00 pm
EDT (GMT -04:00)
Date:
September
22
-
23,
2010
Time:
4:00
-
5:00
PM
Location:
Davis
Centre
(DC)
1304
Speaker: Dr. Vijay Vazirani, College of Computing, Georgia Tech
Abstract:
Let us say that a nonlinear convex program is rational if it has a rational solution that can be written in polynomially many bits, if all its parameters are set to rational numbers. This class turns out to be surprisingly rich -- it captures solutions to several important problems in game theory and mathematical economics. In these two talks, we will show how the primal-dual paradigm was extended from its usual setting of PL-duality theory to obtaining combinatorial algorithms for solving rational convex programs.