Grant: Discovery Grants Program - Individual

Approximation algorithms provide an elegant framework for dealing with intrinsically hard optimization problems, as they provide a guarantee on the "quality" of the solution, obtained in polynomial time. A variety of techniques have been developed over the last three decades for designing approximation algorithms, and these techniques have been quite successful. Approaches based on recursive greedy methods, linear programming, pricing methods, semi-definite programming have been applied to a variety of optimization problems. My research on approximation algorithms for optimization problems would advance the state of art, help train graduate students for the jobs of the future, provide competitive advantage to companies, and develop closer ties with researchers from other countries.