dimacs logo color

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Events

Seminar Details

Matroids and the Greedy Algorithm

  • Start Date: June 12, 2008
  • Event Start Time: 12:00 PM
  • Event End Time: 1:00 PM
  • Organizers: Christine Agnese
  • Seminar Series: REU Seminar
  • Presenter(s): Beth Kupin - Rutgers University
  • Event Location: CoRE 301
  • Abstract: While greedy algorithms are straightforward to think about and easy to program, they usually don't give optimal solutions. It would be nice to know when exactly we can get away with a greedy algorithm, and when we need a more sophisticated tool. Conveniently enough, we can completely characterize which problems will be solvable with a greedy algorithm, based on the underlying structure of the problem. The underlying structure we need is a matroid, a pre-existing algebraic structure worth studying in their own right.