*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Vivek Madan(UIUC)
Monday, February 19, 2018
Klaus 1116 East – 11:00 am
Title: Approximating Multicut and the Demand graph
Abstract: 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.
1. 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.
2. 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.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
