Bottleneck Problems:  Analysis and Approximations
{'Code': '07010000', 'Directorate': {'Abbreviation': 'ENG', 'LongName': 'Directorate For Engineering'}, 'Division': {'Abbreviation': 'ECCS', 'LongName': 'Div Of Electrical, Commun & Cyber Sys'}}
{'SignBlockName': 'Radhakisan Baheti', 'PO_EMAI': None, 'PO_PHON': None}
This research will concentrate on two approaches for analyzing the              effectiveness of algorithms for a class of significant hard                     optimization problems -- the bottleneck problems -- with applications           to location theory, routing, and communication network design.  These           approaches are probabilistic analysis of heuristic algorithms, and              worst case analysis of heuristic algorithms.  Although these approaches         are often considered theoretical in nature, they can have profound              practical implications.  Currently, algorithm design is largely an ad           hoc procedure, whether the goal is to analyze the algorithm based on            its expected or worst case performance, or to provide bounding                  procedures within a branch-and-bound context.  The aims of this                 research are to study the bottleneck problems from several different            viewpoints and to devise unified techniques rather than separate,               haphazard problem-dependent methods.
{'FirstName': 'Dorit', 'LastName': 'Hochbaum', 'PI_MID_INIT': 'S', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Dorit S Hochbaum', 'EmailAddress': 'hochbaum@ieor.berkeley.edu', 'NSF_ID': '000217650', 'StartDate': '07/01/1985', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'University of California-Berkeley', 'CityName': 'BERKELEY', 'ZipCode': '947101749', 'PhoneNumber': '5106433891', 'StreetAddress': '1608 4TH ST STE 201', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'California', 'StateCode': 'CA', 'CONGRESSDISTRICT': '12', 'CONGRESS_DISTRICT_ORG': 'CA12', 'ORG_UEI_NUM': 'GS3YEVSS12N6', 'ORG_LGL_BUS_NAME': 'REGENTS OF THE UNIVERSITY OF CALIFORNIA, THE', 'ORG_PRNT_UEI_NUM': None}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
{'Code': '1454', 'Text': 'SYSTEMS THEORY'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1985&All=true', 'xml': '8501988.xml'}