Research Initiation:  The Structure of NP-Complete Problems
{'Code': '05010100', 'Directorate': {'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Bruce H. Barnes'}
NP-complete problems are among the most interesting and important               optimization problems known.  This class includes literally hundreds of         natural problems from graph theory, routing, scheduling, compiler               optimization and logic.  These problems are especially intriguing               because, although no efficient algorithm is known in the worst case,            many of them can be solved quickly in practice.                                 Traditionally, the work on NP-completeness has focused on the                   complexity and structure of their yes/no questions.  Recently, new              insights have come from looking at a deeper level of structure.  This           investigation continues work on NP-complete problems, focusing on the           structure of their feasible solutions.  Understanding this rich level           of structure will provide a theoretical framework for coping with these         problems in practice.  This theory will then lead to faster algorithms          for solving these problems and a better explanation of their inherent           difficulty.  This research also has applications for finding                    approximation algorithms for NP-complete problems and, in particular,           explaining why some problems can be approximated well and others                cannot.
{'FirstName': 'Mark', 'LastName': 'Krentel', 'EmailAddress': None, 'StartDate': '08/15/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'William Marsh Rice University', 'CityName': 'Houston', 'ZipCode': '770051827', 'PhoneNumber': '7133484820', 'StreetAddress': '6100 MAIN ST', 'CountryName': 'United States', 'StateName': 'Texas', 'StateCode': 'TX'}
[{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}, {'Code': '9145', 'Text': 'SPECIAL PROGRAMS-RESERVE'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8809370.xml'}