Graduate Students
Department Home Undergraduate Graduate CNA CCF Information
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

Apply Now
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 minimum-weight 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