Effective Heuristics for NP-Hard Problems

In many practical situations heuristic algorithms reliably give satisfactory solutions to real-life instances of optimization problems, despite evidence from computational complexity theory that the problems are intractable in general. Our long-term goal is to contribute to an understanding of this seeming contradiction, and to put the construction of heuristic algorithms on a firmer footing,We begin by describing the evolution of successful heuristic algorithms for two problems arising in computational biology:(1) The Colorful Subgraph Problem. Given a graph in which each vertex is labeled with a color, find, if one exists, a connected subgraph containing exactly one vertex of each color.(2) Global Genome Alignment. Given the genomes of several species, an anchor pair is a pair of substrings from two different genomes which appear to be descended from a common ancestral sequence. Given a collection of anchor pairs, construct a multiple alignment maximizing the number of anchor pairs that are aligned against each other.We then discuss a general approach for tuning the parameters and design choices within a given heuristic algorithmic strategy, assuming the availability of a training set of typical problem instances.

R. M. Karp

Talk or presentation