The 2011 Edsger W. Dijkstra Memorial Lecture

The Department of Computer Science (UTCS) at the University of Texas at Austin hosted the Edsger W. Dijkstra Memorial Lecture on November 7, 2011. UTCS welcomed Richard Karp, Professor at the University of California, Berkeley, as the speaker for this event. This lecture series is made possible by a generous grant from Schlumberger to honor the memory of Edsger W. Dijkstra. Watch the 2011 Edsger W. Dijkstra Memorial Lecture!

The 2011 Edsger W. Dijkstra Memorial Lecture:

Richard Karp: “Effective Heuristics for NP-Hard Problems”

Talk Abstract:

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. In particular, we are interested in methods for tuning and validating heuristic algorithms by testing them on a training set of "typical" instances.

About Richard Karp:

Richard M. Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston 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 Professor at the University of California, Berkeley, where he held the Class of 1939 Chair and is currently a University Professor. From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley. From 1995 to 1999 he was a Professor at the University of Washington. During the 1985-86 academic year he was 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 study of combinatorial algorithms. His 1972 paper “Reducibility Among Combinatorial Problems’’ showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking. He has supervised 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 (Carnegie Mellon), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and ten honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science.

About Edsger W. Dijkstra:

Professor Edsger Wybe Dijkstra was a noted pioneer of the science and industry of computing. Born in 1930 in Rotterdam, The Netherlands, he graduated from the Gymnasium Erasmianum in Rotterdam and obtained degrees in mathematics and theoretical physics from the University of Leyden and a Ph.D. in computing science from the University of Amsterdam. He was a professor of mathematics, Eindhoven University of Technology, 1962-1984 and was a Burroughs Corporation research fellow, 1973-1984. He held the Schlumberger Centennial Chair in Computing Sciences at the University of Texas at Austin, 1984-1999, and retired as Professor Emeritus in 1999.

Dijkstra was the 1972 recipient of the ACM Turing Award, often viewed as the Nobel Prize for computing. He was a member of the Netherlands Royal Academy of Arts and Sciences, a member of the American Academy of Arts and Sciences, and a Distinguished Fellow of the British Computer Society. He received the 1974 AFIPS Harry Goode Award, the 1982 IEEE Computer Pioneer Award, and the 1989 ACM SIGCSE Award for Outstanding Contributions to Computer Science Education. In 2002, the C&C Foundation of Japan recognized Dijkstra "for his pioneering contributions to the establishment of the scientific basis for computer software through creative research in basic software theory, algorithm theory, structured programming, and semaphores."

Dijkstra is renowned for the insight that mathematical logic is and must be the basis for sensible computer program construction and for his contributions to mathematical methodology. He is responsible for the idea of building operating systems as explicitly synchronized sequential processes, for the formal development of computer programs, and for the intellectual foundations for the disciplined control of nondeterminacy. He is well known for his amazingly efficient shortest path algorithm and for having designed and coded the first ALGOL 60 compiler. He was famously the leader in the abolition of the GOTO statement from programming.

Dijkstra was a prodigious writer. His entire collection of over thirteen hundred written works was digitally scanned and is accessible at http://www.cs.utexas.edu/users/EWD. He also corresponded regularly with hundreds of friends and colleagues over the years --not by email but by conventional post. He strenuously preferred the fountain pen to the computer in producing his scholarly output and letters.

Dijkstra enriched the language of computing with many concepts and phrases, such as structured programming, separation of concerns, synchronization, deadly embrace, dining philosophers, weakest precondition, guarded command, the excluded miracle, and the famous "semaphores" for controlling computer processes. The Oxford English Dictionary cites his use of the words "vector" and "stack" in a computing context.

Dijkstra died after a long struggle with cancer on August 6, 2002 at his home in Nuenen, the Netherlands.