{"585416":{"#nid":"585416","#data":{"type":"event","title":"Alberto Apostolico Memorial Lecture: Richard M. Karp (UC Berkeley\/Simons Institute)","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlberto Apostolico Memorial Lecture\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003ERichard M. Karp - Simons Institute\/UC Berkeley\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, March\u0026nbsp;13, 2017\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116\u0026nbsp;- 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u0026nbsp;\u003C\/strong\u003E\u003Cem\u003EThe Colorful Connected Subgraph Problem\u003C\/em\u003E\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003EAbstract\u003C\/strong\u003E: \u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EA graph is given, together with a color assigned to each vertex. \u0026nbsp;Many vertices may receive the same color. We consider the NP-hard 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.\u0026nbsp; In particular, we are interested in perfect solutions, in which no color is repeated. Versions of the problem arise in the context of protein-protein interaction networks, social networks and sensor networks.\u0026nbsp; 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. \u0026nbsp;It can also be represented by an integer program with polynomial-bounded numbers of variables and linear constraints. We present a simple fast heuristic algorithm and describe its performance on large 2-dimensional grid graphs, under various specifications of the number of colors and their frequency distribution, using a random model and a semi-random model.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn the random model the color assignment is chosen uniformly at random among assignments with the given frequency distribution. The algorithm reliably gives near-perfect solutions, provided the distribution of color frequencies is not highly skewed.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn the semi-random model a random perfect solution is planted, and the completion of the color assignment is random.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ERegardless 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Manuel Torres (UC Irvine).\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ERichard M. Karp 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. 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 (1995-99) and a Research Scientist at the International Computer Science Institute in Berkeley (1988-1995 and 1999-2012).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EHis research is on combinatorial algorithms, computational complexity and algorithmic methods in genomics and computer networking. He has supervised forty-two 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 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E------------------------------------------------------------------------\u003Cbr \/\u003E\r\nVideos of recent talks are available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Turing award winner speaking on March 13, 11am (Klaus 1116)"}],"uid":"32895","created_gmt":"2016-12-30 07:51:40","changed_gmt":"2017-04-13 21:13:30","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-03-13T12:00:00-04:00","event_time_end":"2017-03-13T13:00:00-04:00","event_time_end_last":"2017-03-13T13:00:00-04:00","gmt_time_start":"2017-03-13 16:00:00","gmt_time_end":"2017-03-13 17:00:00","gmt_time_end_last":"2017-03-13 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EEric Vigoda\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}