Expedited Novel Research Award; Local Averaging - A         Deterministic Analogue of Simulated Annealing
{'Code': '07010000', 'Directorate': {'LongName': 'Directorate For Engineering'}, 'Division': {'LongName': 'Div Of Electrical, Commun & Cyber Sys'}}
{'SignBlockName': 'Radhakisan S. Baheti'}
Simulated annealing has had success in solving complex computational            problems by using a form of average to smooth out the local optima of           a cost functions, thereby enabling it to make progress towards the              global optimum.  Based on this idea, PI proposes a new approach called          local averaging to derive information about the variation of the cost           function.  He defines a normalized cost of a state to be its absolute           cost minus the average cost of all states.  He has discovered that for          several NP-complete problems, including the traveling salesman problem          and the min-cut graph partitioning problem, the average normalized              cost of the neighboring states of any state is a constant multiple a            of the normalized cost of that state, where 0 < a < 1.  Using this              result, he has shown that local optima of any of these problems have            to be better than the average cost of all states.  Also, applying the           same result, it is found that NP-complete problems satisfy an equation          which strongly resembles certain wave equations of mathematical                 physics.                                                                                                                                                        An analysis of simulated annealing is carried out, based on the                 neighborhood structure of NP-complete problems.  Simulated annealing            is shown to satisfy a simple continuity equation, based on which it is          suggested that the algorithm can be implemented with a combination of           random moves and greedy moves.  The relative fraction of random moves           is decreased with temperature.  This implementation is faster than the          standard one, since no cost calculations have to be done for the                random moves.
{'FirstName': 'Lov', 'LastName': 'Grover', 'EmailAddress': None, 'StartDate': '01/15/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Cornell University', 'CityName': 'Ithaca', 'ZipCode': '148502820', 'PhoneNumber': '6072555014', 'StreetAddress': '373 Pine Tree Road', 'CountryName': 'United States', 'StateName': 'New York', 'StateCode': 'NY'}
{'Code': '1454', 'Text': 'SYSTEMS THEORY'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8803659.xml'}