DIMACS - Graduate Student Combinatorics Seminar

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.

See: http://math.rutgers.edu/~klm296/GCS/index.html