{"586435":{"#nid":"586435","#data":{"type":"event","title":"ARC Colloquium: Philip Klein (Brown)","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EPhilip N. Klein (Brown)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 27, 2017\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003EApproximation Schemes for Planar Graphs: A Survey of Methods\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nIn addressing an NP-hard problem in combinatorial optimization, one way to cope is to use an\u0026nbsp;\u003Cem\u003Eapproximation scheme\u003C\/em\u003E, an algorithm that, for any given\u0026nbsp;\u03f5\u0026gt;0, produces a solution whose value is within a\u0026nbsp;1+\u03f5\u0026nbsp;factor of optimal. For many problems on graphs, obtaining such accurate approximations is NP-hard if the input is allowed to be any graph but is tractable if the input graph is required to be planar.\u0026nbsp;\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nResearch on polynomial-time approximation schemes for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983). Since then, however, the scope of problems amenable to approximation has broadened considerably. In this talk I will outline some of the approaches used, especially those that have led to recent results.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESpeaker\u0026#39;s Bio\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPhil Klein is Professor of Computer Science at Brown University.\u0026nbsp; He\u0026nbsp;received an A.B. in Applied Mathematics from Harvard and a Ph.D. in\u0026nbsp;Computer Science from MIT.\u0026nbsp; His research area is algorithms for\u0026nbsp;finding optimal and approximately optimal solutions to optimization\u0026nbsp;problems in graphs and networks.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EHe is an ACM Fellow, a recipient of the Presidential Young\u0026nbsp;Investigator Award, and a recipient of Brown University\u0026#39;s Philip\u0026nbsp;J. Bray Award for Excellence in Teaching in the Sciences.\u0026nbsp; He was the\u0026nbsp;SODA Program Committee Chair in 2017, and a Radcliffe Institute\u003Cbr \/\u003E\r\nFellow in 2016-2017.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/cs.brown.edu\/people\/klein\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos 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\/em\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":"Approximation Schemes for Planar Graphs: A Survey of Methods (Klaus 1116 E at 11am)"}],"uid":"32895","created_gmt":"2017-01-25 14:38:16","changed_gmt":"2017-04-17 16:13:02","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-03-27T12:00:00-04:00","event_time_end":"2017-03-27T13:00:00-04:00","event_time_end_last":"2017-03-27T13:00:00-04:00","gmt_time_start":"2017-03-27 16:00:00","gmt_time_end":"2017-03-27 17:00:00","gmt_time_end_last":"2017-03-27 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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}