Université du Luxembourg

PhD Seminar at the Department of Mathematics (DMATH)

  • Main page
  • about
  • DMATH
  • Recent sessions
  • 2020
  • 2019
  • 2018
  • 2017
  • Archive
  • 2015 – 2016
  • 2014 – 2015
  • 2013 – 2014
  • 2012 – 2013
  • 2011 – 2012
  • 2010 – 2011
  • 2009 – 2010
  • 2008 – 2009
  • 26 February 2020 Alisa GOVZMANN, Parametrized complexity of bin-packing
    Abstract

    I will first introduce and explain one of the seven famous millennium problems posed by the Clay Mathematics Institute and known as the P vs. NP problem. Then I will analyze the bin-packing problem, which is known to be NP-complete and hence might be used in order to solve the P vs. NP problem. I will introduce a runtime analysis method known as parametrized complexity and show a nice parametrized algorithm for bin-packing.

Created by Robert Baumgarth | Last updated on 27 May 2020