OR Student Seminar - A Problem Not in P, Marton Benedek (University of Southampton) Seminar

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.