Richard M. Karp (University of California at Berkeley and International Computer Science Institute)
Wednesday, 16.11.2011, 14:30
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.