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.