Publication Details
Title: Effective Heuristics for NP-Hard Problems
Author: R. M. Karp
Group: Algorithms
Date: August 2011
PDF: [Not available online]
Overview:
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 Information:
Presented at the Michael Rabin Celebration, Cambridge, Massachusetts
Bibliographic Reference:
R. M. Karp. Effective Heuristics for NP-Hard Problems. Presented at the Michael Rabin Celebration, Cambridge, Massachusetts, August 2011
Author: R. M. Karp
Group: Algorithms
Date: August 2011
PDF: [Not available online]
Overview:
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 Information:
Presented at the Michael Rabin Celebration, Cambridge, Massachusetts
Bibliographic Reference:
R. M. Karp. Effective Heuristics for NP-Hard Problems. Presented at the Michael Rabin Celebration, Cambridge, Massachusetts, August 2011