DIMACS - Graduate Student Combinatorics Seminar

Title: Matroids and Greedy Algorithms

Speaker: Andrew Lohr, Rutgers University

Date: Wednesday, November 8, 2017 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Greedy algorithms are great when they work. They are often very fast and simple to implement. For many problems, though, it it can be misleading, sometimes giving a really far from optimal solution. We'll see how a greedy algorithm working relates to the problems having a matroid structure.

See: http://www.math.rutgers.edu/~yb165/GCS.html