Tools for Stochastic Analysis of NP-Complete Problems - II
{'Code': '05010100', 'Directorate': {'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Bruce H. Barnes'}
A large class of optimization problems, called NP-complete problems,            are likely to be intractable.  Due to the great difficulty of finding           the optimum solutions of these problems, researchers are turning                towards the (maybe more significant) search of an approximation                 solution in the "average" case of a suitable stochastic model.  A               typical NP-complete problem is the Bin-Packing problem, which requires          finding the minimum number of unit size bins needed to pack a given             collection of items of size less than or equal to 1.  In the most               natural model of stochastic bin packing, sizes of items are distributed         independently according to a given distribution u.  (No special                 assumptions are made on u).  Abstract mathematical tools have been used         to obtain with relative ease rather unexpected results about optimal            packing in this model.  This project will investigate the bin packing           problem, and its variations such as dual bin packing and strip packing,         a stochastic version of the traveling salesman problem.
{'FirstName': 'WanSoo', 'LastName': 'Rhee', 'EmailAddress': None, 'StartDate': '07/15/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Ohio State University Research Foundation -DO NOT USE', 'CityName': 'Columbus', 'ZipCode': '432101016', 'PhoneNumber': '6146888734', 'StreetAddress': '1960 KENNY RD', 'CountryName': 'United States', 'StateName': 'Ohio', 'StateCode': 'OH'}
{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8801517.xml'}