Primal-Dual Algorithms for Rational Convex Programs

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.