Skip to main navigationSkip to main content
The University of Southampton
Southampton SIAM Student Chapter

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

Privacy Settings