Wednesday, May 31, 2017 - 11:00am to 12:00pm
Location:7101 Gates Hillman Centers
Speaker:VIVEK MADAN, Ph.D. Student http://vmadan2.web.engr.illinois.edu/
A cut problem is specified by a graph G and property X. The goal is to remove edges/vertices (E′/V′) such that the remaining graph satisfies property X. We investigate a labeling view of some of the cut problems based on the structural properties of G−E′/V′ and improve existing results. In particular, we study multiway cut, multicut and subset feedback set problems. Some of the results include simpler approximation algorithm for multiway cut, unique games hardness of k−ϵ for separating k pairs in directed graph, and a new LP-based constant factor approximation algorithm for subset feedback vertex set.