CSpecial Talk: Effective Heuristics for NP-Hard Problems

Richard M. Karp (University of California at Berkeley and International Computer Science Institute)

Wednesday, 16.11.2011, 14:30

Room 337-8 Taub Bld.

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.

As a step in this direction we describe the evolution of a succesful heuristic algorithm By Erick Moreno Centeno and the speaker for the following Global Genome Alignment problem: 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. Such an alignment exhibits the common evolutionary ancestry of the set of species.

We then use the Global Genome Alignment problem to illustrate 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. This approach leads to a decision-theoretic problem related to the Multi-Armed Bandit Problem.

As a step in this direction we describe the evolution of a succesful heuristic algorithm By Erick Moreno Centeno and the speaker for the following Global Genome Alignment problem: 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. Such an alignment exhibits the common evolutionary ancestry of the set of species.

We then use the Global Genome Alignment problem to illustrate 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. This approach leads to a decision-theoretic problem related to the Multi-Armed Bandit Problem.