Design and Analysis of Algorithms for Coping with NP-Hardness

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

9713482 Hochbaum This project will study three approaches to devising algorithms and analyzing their effectiveness for obtaining solutions to hard optimization problems. These three approaches (1) probabilistic analysis of heuristic algorithms, (2) worst case analysis of heuristic algorithms, and (3) implicit enumerative algorithm design are often pursued separately, since the techniques involved are usually quite different. Considerable insight can be gained by employing all three approaches in parallel. Algorithm design is largely an ad hoc procedure, whether the goal is to devise an algorithm with good performance based on its average or worst case performance, or to provide bounding procedures within a branch-and-bound context. This research will focus on devising unified techniques applicable to large problem classes. The research is expected to generate, among other outcomes, a unified technique based on the choice of problem formulation and the application of specific types of transformation on the formulations that make obtaining good feasible solutions easy, at a limited loss of optimality. This technique has enormous potential for deriving approximation algorithms with good performance and generating tight bounds that are useful for enumerative algorithms. The technique is also a unified approach applicable to a wide range of problems. If the investigation using all three approaches is successful, it will provide new and useful methods for improving the quality of solutions for problems in areas varying from telecommunications and scheduling to locations, clustering and circuit testing.