Design and Analysis of Algorithms for Coping with NP-Hardness

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The grant is to study three approaches for 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 algorithm; and (3) (implicit) enumerative algorithm design-are often pursued separately, since the techniques involved are usually quite different. The first two approaches are often considered theoretical in nature, yet they can have profound practical implications. It is proposed that 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. The grant is to devise unified techniques applicable to certain problem classes and expand the range of applications of the developed unified techniques. The research is to address, among other topics, a specific technique, which called factor-2-transformations. This technique has enormous potential for deriving constant factor approximations and tight bounds that are useful for enumerative algorithms applicable to a wide range of problems. In addition, the technique leads to so-called "persistency" results that permit the fixing of some variables within an enumerative procedure and thus limiting the search space. This technique has already been shown to have a wide range of applications in diverse areas ranging from scheduling, to layout problems, to geometric planning and packing problems, to location problems and to generalize satisfiability problems.