event
Alberto Apostolico Memorial Lecture: Richard M. Karp (UC Berkeley/Simons Institute)
Primary tabs
Alberto Apostolico Memorial Lecture
Richard M. Karp  University Professor at University of California, Berkeley; Director of the Simons Institute for the Theory of Computing; 1985 Turing Award Winner
Monday, March 13, 2017
Klaus 1116  11:00 am (lunch to follow in the Atrium. Please RSVP here!)
Livestream: http://www.cc.gatech.edu/eventwebcast
Title: The Colorful Connected Subgraph Problem
Abstract:
A graph is given, together with a color assigned to each vertex. Many vertices may receive the same color. We consider the NPhard problem of finding a connected subgraph with a minimum number of vertices, such that the subgraph must contain at least one vertex of each color. In particular, we are interested in perfect solutions, in which no color is repeated. Versions of the problem arise in the context of proteinprotein interaction networks, social networks and sensor networks. The problem (or even a generalization in which the edges of the graph are weighted) can be solved by a dynamic programming in time polynomial in the size of the graph but exponential in the number of colors. It can also be represented by an integer program with polynomialbounded numbers of variables and linear constraints. We present a simple fast heuristic algorithm and describe its performance on large 2dimensional grid graphs, under various specifications of the number of colors and their frequency distribution, using a random model and a semirandom model.
In the random model the color assignment is chosen uniformly at random among assignments with the given frequency distribution. The algorithm reliably gives nearperfect solutions, provided the distribution of color frequencies is not highly skewed.
In the semirandom model a random perfect solution is planted, and the completion of the color assignment is random.
Regardless of the frequency distribution the algorithm reliably produces perfect solutions. In this case we extend the algorithm to generate many perfect solutions, and report on its performance.
This is joint work with Manuel Torres (UC Irvine).
Bio:
Richard M. Karp attended Boston Latin School and Harvard University, receiving his Ph.D. in 1959. From 1959 to 1968, he was a member of the Mathematical Sciences Department at IBM Research. He is a University Professor at UC Berkeley and director of the Simons Institute for the Theory of Computing. He joined the Berkeley faculty in 1968 and has also been a faculty member at the University of Washington (199599) and a research scientist at the International Computer Science Institute in Berkeley (19881995 and 19992012).
Karp's research is on combinatorial algorithms, computational complexity, and algorithmic methods in genomics and computer networking. He has supervised 42 Ph.D. dissertations. Honors and awards include: U.S. National Medal of Science, Turing Award, Kyoto Prize, Fulkerson Prize, Harvey Prize (Technion), Centennial Medal (Harvard), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and 10 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.
Groups
Status

Workflow Status:
Published 
Created By:
Birney Robert 
Created:
01/12/2017 
Modified By:
Fletcher Moore 
Modified:
04/13/2017
Categories
Target Audience