Algorithm Engineering for NP-Complete Problems

点击翻译按钮获取中文摘要

This project will study the impact that advanced combinatorial algorithmtechniques and data structures can have on the performance ofheuristic search, both in theory and in the context ofbuilding a general-purpose combinatorial optimization engine.This engine will be applied to yield quality implementations ofheuristics for twenty NP-complete problems which arise commonly in practice.This approach focuses attention on identifying versatile high-performanceapproaches to local optimization. Further, it suggests a variety ofnew lines of theoretical research which will lead to improved optimizationalgorithms.The impact of this research revolves around (1) the development of newcombinatorial algorithms and data structures supporting powerfulcrossover, mutation, and cycle-avoidance operations, and mapping energylandscapes, as well as provably good approximations, (2) a systematicstudy of the performance of local search variants including simulatedannealing, genetic algorithms, and tabu search, (3) the development ofuseful software for research, industrial, and educational applications,and (4) the creation of a new competitive forum for assessing the stateof the art in algorithm engineering.