Presidential Young Investigator Award (Computer Research)

在高效算法的设计和分析中，人们正在研究各种各样的问题。研究的主要领域是设计NP-hard优化问题的有效近似算法。尽管这一领域在过去二十年中受到了很多关注，但在统一结果的方式上仍然知之甚少。为了发展近似算法的最坏情况分析理论，本研究寻求适用于许多领域问题的设计和分析技术。正在开发的工具可以解释为什么某些问题很容易接近，而其他问题则不然。第二个正在研究的领域是组合问题并行计算的算法技术。尽管有效的并行算法现在存在于越来越多的问题中，但仍然很少有对各种问题有用的适当算法原语的赞赏。随机化已被证明是算法设计的许多领域的有用工具，特别是对于并行和分布式计算。在这一领域的研究仍在继续，特别是在其对近似算法的最坏情况分析的适用性方面。他被总统青年调查委员会评为杰出的计算机科学家。

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.