Effective Heuristics for NP-Hard Problems

TitleEffective Heuristics for NP-Hard Problems
Publication TypeMiscellaneous
Year of Publication2011
AuthorsKarp, R. M.
Other Numbers3191

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.

Bibliographic Notes

Presented at the Michael Rabin Celebration, Cambridge, Massachusetts

Abbreviated Authors

R. M. Karp

ICSI Research Group


ICSI Publication Type

Talk or presentation