A Problem Not in P Seminar
- Time:
- 15:00 - 16:00
- Date:
- 13 December 2017
- Venue:
- The Ketley Room (B54 - level 4)
Event details
Ever wondered why the greedy algorithm works at all? Always considered NP-hard problems as hard? Would like to get a million dollars (plus some fame) easily? In this talk I attempt to address these questions by giving a brief introduction into the theory of matroids. We will look into different kind of matroids and matroid problems (with a very little peek into complexity theory), and their connection to the questions raised above. The primary motivation of the talk is to provide some insight into something hopefully interesting and new, such as a problem that does not lie in P. Also, as the festive season approaches, I attempt to spice the talk up with anonymous quotes from lecturers of the department as a sort of holiday treat.
Speaker information
Marton Benedek, Postgraduate Research Student of Joerg Fliege and Tri-Dung Nguyen