Presidential Young Investigator Award (Computer Research)

点击翻译按钮获取中文摘要

A wide range of problems in the design and analysis of efficient algorithm is being investigated. The primary area of investigation is the design of efficient approximation algorithms for NP-hard optimization problems. Although this area has received much attention over the past two decades, there is still little known in the way of unifying results. In an attempt to develop a theory of worst-case analysis of approximation algorithms, this research seeks techniques of design and analysis that are applicable to problems from many areas. Under development are tools for explaining why certain problems are easily approximable, whereas others are not. A second area under investigation is that of algorithmic techniques for parallel computation for combinatorial problems. Although efficient parallel algorithms now exist for an increasing number of problems, there is still little appreciation of the appropriate algorithmic primitives that will be useful for a variety of problems. Randomization has proved to be a useful tool in many areas of algorithm design, particularly for parallel and distributed computing. Investigations, are continuing in this area, and in particular, in its applicability to worst-case analysis of approximation algorithms. The PI has been judged to be an outstanding computer scientist by the Presidential Young Investigator panel.