This project focuses on research and teaching activities in the general area of approximation and online algorithms. Many optimization problems are intractable, so it is natural to approximate the optimum instead of computing an exact solution. With this insight, the past two decades have seen tremendous activity in approximation algorithms, to the point where the approximability of some basic problems is well-understood. In addition to this enhanced understanding of the computational complexity of optimization problems, an ever-increasing set of techniques and tools to attack problems old and new have been proposed. Given this situation, it is natural to take a two-pronged plan of research: while continuing to resolve some of the long-standing open problems of interest, the investigator will concurrently extend the scope of the new techniques, and also investigate more expressive models and problem abstractions that attempt to capture the rich diversity of optimization problems that arise in practice.
Along these lines, a major theme of this research is to investigate how to solve optimization problems in the presence of partial information, and hence uncertainty. This is something often considered in practice: based only on probabilities of various events happening in the future, and subject to constraints on resources (time/money), a system must make decisions. In the spirit of computational thinking, this research is aimed at formalizing some of these problems so that efficient solutions can be found for more realistic models than the traditional worst-case model. Research progress on these questions will advance the state-of-the-art in decision-making under uncertainty, an area lying at the intersection of computer science, operations research, and decision theory. This research will also be instrumental in training of graduate and undergraduate students.
