Research in Combinatorial Optimization
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'name not available', 'PO_EMAI': None, 'PO_PHON': None}
Research is being conducted in five areas: submodular function                  minimization, optimal subgraphs, "meta-algorithms," scheduling theory,          computational geometry, and parallel computation.                                                                                                               It is known that, in principle, the submodular function minimization            problem can be solved by a polynomial-bounded algorithm based on the            ellipsoid method of linear programming.  The objective of this research         is to produce a computationally practical algorithm that could, for             example, be utilized as a subroutine in polymatroidal network flow              computations.                                                                                                                                                   The proposed research on "meta-algorithms" is an outgrowth of previous          work on linear-time algorithms for solving optimal subgraph problems.           The input to a meta-algorithm will be a problem description and the             output an algorithm for solving the given problem.                                                                                                              The work on scheduling theory is a continuation of the PI's previous            research.  Work is in progress on a number of open problems, such as the        three-processor problem and the single-processor total tardiness                problem.                                                                                                                                                        The research in progress in computational geometry concerns the                 rectilinear Steiner problem and problems concerning covering of                 rectilinear polygons with rectangles.  These problems were suggested by         issues in VLSI design.                                                                                                                                          The work in parallel and distributed computation concerns methods for           solving very large NP-hard problems.  It is proposed to continue work on        methods for randomized subproblem assignment and load balancing in a            multiprocessor system.                                                                                                                                          The research concerns theoretical problems that are motivated by the            need for computationally practical solutions for problems from a variety        of sources.  Results that impact computing practice are expected.
{'FirstName': 'Eugene', 'LastName': 'Lawler', 'PI_MID_INIT': 'L', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Eugene L Lawler', 'EmailAddress': None, 'NSF_ID': '000300163', 'StartDate': '07/01/1987', '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': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1987&All=true', 'xml': '8704184.xml'}