Edsger W. Dijkstra Memorial Lecture - Sponsored by Schlumberger - Richard Karp/University Professor, University of California at Berkeley & International Computer Science Institute, "Effective Heuristics for NP-Hard Problems", ACES 2.302

Contact Name: 
Jenna Whitney
Nov 7, 2011 4:00pm - 5:30pm

There is a sign-up schedule for this event that can be found at



you Schlumberger, for sponsoring this event!


ype of Talk: Edsger W. Dijkstra Memorial Lecture


Richard Karp/University Professor, University of California at Berkeley &

International Computer Science Institute

Talk Audience: UTCS Graduate

Students, Undergraduate Students, Faculty, Staff and Outside Interested


Date/Time: Monday, November 7, 2011, 4:00 p.m. - 5:30 p.m.

Location: ACES 2.302

Host: Tandy Warnow

Talk Title: Effectiv

e Heuristics for NP-Hard Problems

Talk Abstract:
In many practical s

ituations heuristic algorithms reliably give satisfactory solutions to real

-life instances of optimization problems, despite evidence from computatio

nal complexity theory that the problems are intractable in general. Our lo

ng-term goal is to contribute to an understanding of this seeming contradic

tion, and to put the construction of heuristic algorithms on a firmer foot

ing. In particular, we are interested in methods for tuning and validating
heuristic algorithms by testing them on a training set of "typical" instan


As a step in this direction we describe the evolution and validat

ion of two heuristic algorithms.

(1) A generic algorithm for the class
of implicit hitting set problems, which includes feedback vertex set and

feedback edge set problems, the max-cut problem, the Steiner tree proble

m, the problem of finding a maximum feasible subset of a set of linear ine

qualities, matroid intersection problems and a problem of global genome al

ignment (joint work with Erick Moreno Centeno).

(2) The Colorful Subgr

aph Problem: given a graph in which each vertex is assigned a color from a

set S, find the smallest connected subgraph containing at least one vertex
of each color in S. (joint work with Shuai Li).

In closing, we will

discuss the application of decision theory to the problem of choosing the

best variant of a given algorithm, based on observations of algorithmic pe

rformance on a training set of instances.

Speaker Bio:
Richard M. Ka

rp was born in Boston, Massachusetts on January 3, 1935. He attended Bost

on Latin School and Harvard University, receiving the Ph.D. in 1959. From

1959 to 1968 he was a member of the Mathematical Sciences Department at IBM
Research. From 1968 to 1994 and from 1999 to the present he has been a Pro

fessor at the University of California, Berkeley, where he held the Class
of 1939 Chair and is currently a University Professor. From 1988 to 1995 a

nd 1999 to the present he has been a Research Scientist at the Internationa

l Computer Science Institute in Berkeley. From 1995 to 1999 he was a Profe

ssor at the University of Washington. During the 1985-86 academic year he w

as the co-organizer of a Computational Complexity Year at the Mathematical

Sciences Research Institute in Berkeley. During the 1999-2000 academic year
he was the Hewlett-Packard Visiting Professor at the Mathematical Sciences
Research Institute.

The unifying theme in Karp''s work has been the s

tudy of combinatorial algorithms. His 1972 paper "Reducibility Among Combi

natorial Problems'''' showed that many of the most commonly studied combina

torial problems are NP-complete, and hence likely to be intractable. Much

of his work has concerned parallel algorithms, the probabilistic analysis

combinatorial optimization algorithms and the construction of randomiz

ed algorithms for combinatorial problems. His current activities center aro

und algorithmic methods in genomics and computer networking. He has supervi

sed thirty-nine Ph.D. dissertations.

His honors and awards include: U.

S. National Medal of Science, Turing Award, Kyoto Prize, Fulkerson Prize

, Harvey Prize (Technion), Centennial Medal (Harvard), Dickson Prize (Ca

rnegie Mellon), Lanchester Prize, Von Neumann Theory Prize, Von Neumann

Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Le

cturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize an

d ten honorary degrees. He is a member of the U.S. National Academies of S

ciences and Engineering, the American Philosophical Society and the French
Academy of Sciences, and a Fellow of the American Academy of Arts and Sci

ences, the American Association for the Advancement of Science, the Assoc

iation for Computing Machinery and the Institute for Operations Research an

d Management Science.