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


Abstract:

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