Effective Heuristics for NP-Hard Problems
Title | Effective Heuristics for NP-Hard Problems |
Publication Type | Miscellaneous |
Year of Publication | 2011 |
Authors | Karp, R. M. |
Other Numbers | 3191 |
Abstract | 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 | Algorithms |
ICSI Publication Type | Talk or presentation |