Special Theory Seminar

Wednesday, May 31, 2017 - 11:00am to 12:00pm


7101 Gates Hillman Centers


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.

For More Information, Contact:


Special Seminar