Presidential Young Investigator Award (Computer Research)
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Dana S. Richards'}
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.
{'FirstName': 'David', 'LastName': 'Shmoys', 'EmailAddress': 'shmoys@cs.cornell.edu', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Massachusetts Institute of Technology', 'CityName': 'Cambridge', 'ZipCode': '021394301', 'PhoneNumber': '6172531000', 'StreetAddress': '77 MASSACHUSETTS AVE', 'CountryName': 'United States', 'StateName': 'Massachusetts', 'StateCode': 'MA'}
{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1986&All=true', 'xml': '8657688.xml'}