Graduate Programs
Graduate Home
Ph D Programs
Masters Degree
Ph D Program Requirements
Course Descriptions
Current Courses
Admissions
Current Graduate Students
Graduate Student Seminar
SIAM Chapter Seminar
Recent Graduates
Incoming Students

Graduate Seminar
Brian Kell Carnegie Mellon University Title: Matroids and greedy algorithms Abstract: Combinatorial optimization is the study of problems that ask for an "optimal" element of a finite set of objects; that is, an element that maximizes or minimizes a given objective function. Examples include the problem of finding a minimumweight spanning tree in a graph and the problem of finding an optimal order in which to perform a set of tasks with deadlines. Often the most direct way to attempt a solution to such a problem is a greedy algorithm, which makes maximum local improvements to the objective function at each step and never backtracks. Perhaps surprisingly, greedy algorithms provide optimal solutions for a diverse class of problems. Why is this true? To answer this question, I will introduce matroids and show that many apparently different greedy algorithms are really the same algorithm applied in various settings. Date: Wednesday, February 12, 2014 Time: 5:30 pm Location: Wean Hall 8220 Submitted by: Brian Kell 