Title: Approximation Algorithm Techniques via Set Cover
Speaker: Matthew Oster, Rutgers University
Date: Wednesday, April 25, 2012 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
For any optimization problem whose underlying decision problem is NP-Complete, no exact polynomial-time algorithm can exist, assuming P != NP. Naturally, an alternative approach is to attempt to design polynomial-time heuristics which yield provably "good" solution approximations. In this talk I will discuss some of the fundamental techniques in a line of research called Theory of Approximation Algorithms. Greedy and combinatorial methods, rounding, and primal-dual schema (if time permits) will all be demonstrated on the combinatorial problem Set Cover.