"Heuristic Approaches to Optimization with Applications"

This progress report covers the twelve months of funding on this grant since my previ-ous progress report (August 1999). This grant covers two distinct lines of work: (1) the development of algorithms and implementations of heuristic search with applications, and (2) theoretical research on combinatorial algorithms and optimization. As detailed below, substantial progress has been made in both areas since my last progress report. The renewal grant began on January 1, 2000. This grant is supporting four PhD students starting September 1, meeting the scheduled expenditure for this fiscal year. Our work has proven interesting to a large number of Navy personnel, as documented by the WWW hits below. 2 Environments for Combinatorial Computing We have made progress this year on several projects related to combinatorial computing: • Enhancements to Combinatorica- We [1] have made substantial progress on our effort to build an improved version of our combinatorial computing environment Combinator-ica. Our primary goals are improved algorithmic performance and a better user inter-face. We have completed an alpha-release of the software, as well as documentation of the new features; all available a