{"642859":{"#nid":"642859","#data":{"type":"event","title":"ARC Colloquium: Rico Zenklusen (ETH Zurich)","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\u003ERico Zenklusen (ETH Zurich)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 1, 2021\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EBridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EThe Connectivity Augmentation Problem (CAP) is one of the most basic survivable network design problems. It asks about increasing the edge-connectivity of a graph G by one unit through adding a smallest number of additional edges from a given set. If the edge-connectivity of G is odd, it reduces to a heavily studied special case known as the Tree Augmentation Problem (TAP). Despite significant recent progress on TAP, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain an approximation algorithm for CAP with guarantee better than 2 by presenting a 1.91-approximation based on techniques disjoint from recent TAP advances.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nIn this talk, I will present new methods that allow for leveraging insights and techniques from TAP to approach CAP. Combined with a novel analysis technique, we obtain a 1.393-approximation for CAP. This significantly improves in a unified way on the previously best approximation factor for CAP (1.91) and also TAP (1.458).\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThis is joint work with Federica Cecchetto and Vera Traub.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/math.ethz.ch\/ifor\/people\/rico-zenklusen.html\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: \u003C\/em\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches -Virtual via Bluejeans at 11:00am"}],"uid":"27544","created_gmt":"2021-01-12 17:36:49","changed_gmt":"2021-02-16 16:16:18","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-03-01T11:00:00-05:00","event_time_end":"2021-03-01T12:00:00-05:00","event_time_end_last":"2021-03-01T12:00:00-05:00","gmt_time_start":"2021-03-01 16:00:00","gmt_time_end":"2021-03-01 17:00:00","gmt_time_end_last":"2021-03-01 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":"177814","name":"Postdoc"},{"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":""}}}