{"602340":{"#nid":"602340","#data":{"type":"event","title":"ARC Colloquium:  Vivek Madan (UIUC)","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\u003EVivek Madan(UIUC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 19, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 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:\u0026nbsp; \u003C\/strong\u003EApproximating Multicut and the Demand graph\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; The Multicut problem is a generalization of the classical $s-t$ cut problem to multiple pairs. Given an edge-weighted directed or undirected supply graph G=(V,E), and k source-sink pairs (s1,t1),\\dots,(sk,tk), the goal is to remove a minimum weight subset of edges in G such that all the given (si,ti) pairs are disconnected. Over the past 30 years, Multicut has attracted significant attention in approximation algorithms, and a variety of results have been obtained for general and special classes of supply graphs. Motivated by new applications, I study Multicut with a focus on the demand graph (graph with an edge set {(si,ti) \\mid i \\in [k]}). We obtain several new approximability and inapproximability results based on a labeling viewpoint of the problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E1.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Approximation algorithms: We present a unified 2-approximation algorithm for undirected multicut problem for tK2-free demand graphs when t is a fixed constant. For directed multiway cut we significantly simplify the 2-approximation algorithm of Naor and Zosin from twenty years ago; our rounding strategy yields a constant factor for much more general classes of demand graphs. For the problem of linear-k-cut (a special case of directed multicut which motivated this work), we show some initial results and prove a tight \\sqrt{2}-approximation algorithm when k=3.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E2.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Hardness of approximation: We prove that for a class of demand graphs, undirected multicut admits a constant factor approximation algorithm iff the class is tK2-free for some constant t. For directed multicut, we prove that assuming the Unique Games Conjecture (UGC), hardness of approximation matches the flow-cut gap for any fixed bi-partite demand graph. As a consequence, we prove that for any fixed k \\ge 2, there is no (k-eps) approximation algorithm for Multicut with k pairs, assuming UGC.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/vmadan2.web.engr.illinois.edu\/\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=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Approximating Multicut and the Demand Graph - Klaus 1116 East at 11:00am"}],"uid":"27544","created_gmt":"2018-02-14 12:53:08","changed_gmt":"2018-02-14 20:37:21","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-19T11:00:00-05:00","event_time_end":"2018-02-19T12:00:00-05:00","event_time_end_last":"2018-02-19T12:00:00-05:00","gmt_time_start":"2018-02-19 16:00:00","gmt_time_end":"2018-02-19 17:00:00","gmt_time_end_last":"2018-02-19 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":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}