Title: Planar Approximation Schema
Speaker: Justin Semonsen, Rutgers University
Date: Wednesday, December 2, 2015 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
This talk will give an overview the special properties of planar graphs and how these can be exploited to get a linear time epsilon approximation for independent set. We will also develop the key ideas for the development of linear-time approximation schema for other NP-hard problems in planar graphs.