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
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.