Algorithm Engineering for NP-Complete Problems

Suny At Stony Brook, Stony Brook NY

Investigators

Abstract

This project will study the impact that advanced combinatorial algorithm techniques and data structures can have on the performance of heuristic search, both in theory and in the context of building a general-purpose combinatorial optimization engine. This engine will be applied to yield quality implementations of heuristics for twenty NP-complete problems which arise commonly in practice. This approach focuses attention on identifying versatile high-performance approaches to local optimization. Further, it suggests a variety of new lines of theoretical research which will lead to improved optimization algorithms. The impact of this research revolves around (1) the development of new combinatorial algorithms and data structures supporting powerful crossover, mutation, and cycle-avoidance operations, and mapping energy landscapes, as well as provably good approximations, (2) a systematic study of the performance of local search variants including simulated annealing, genetic algorithms, and tabu search, (3) the development of useful software for research, industrial, and educational applications, and (4) the creation of a new competitive forum for assessing the state of the art in algorithm engineering.