The theory of NP Completeness has shown that several naturally occurring problems are unlikely to have polynomial time algorithms. One approach to overcome this fundamental intractability for optimization problems has been to shift the focus from exact solutions to obtaining approximate solutions. The study of approximation algorithms has thus emerged as a rich and exciting field and recent advances have led to good approximation algorithms for several fundamental optimization problems. Despite these developments, several interesting and difficult open problems remain. A primary focus of this career development plan is studying the approximability of fundamental problems and attempting to close such gaps in our understanding.
The broad research goals of this career development plan are the following:
1. Developing new tools to devise approximation algorithms for problems on directed graphs. 2. Developing new techniques for metric approximations and embeddings as building blocks for approximation. 3. Investigating a systematic way to obtain and exploit strengthened SDPs as well as the use of strengthened SDPs for graph partitioning minimization problems and ordering problems. 4. Devise techniques to deal with scheduling problems with precedence constraints. 5. Extend the machinery of approximation algorithms to new settings such as information theoretic and algebraic problems.
The research program will involve students at all levels, from undergraduate projects on understanding the quality of LP and SDP relaxations through computational experiments, to the mathematical research suitable for Ph.D. students. The educational component of this project includes the development of courses geared towards disseminating new algorithmic ideas outside the theoretical computer science community; the techniques developed in the latest research will be distilled into new graduate and undergraduate courses. Course materials developed for such new courses will be made freely available to enable similar courses to be taught elsewhere.
