Skip to content (access key 's')
Logo of Technion
Logo of CS Department


CSpecial Talk: Effective Heuristics for NP-Hard Problems
event speaker icon
Richard M. Karp (University of California at Berkeley and International Computer Science Institute)
event date icon
Wednesday, 16.11.2011, 14:30
event location icon
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.
[Back to the index of events]