Kolloquiumsvortrag (INF), Dr. Matthias Mnich, Uni Bonn / am 01.06.2018

01.06.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

Titel: Multivariate Algorithms for Machine Scheduling Problems

Abstract: Machine scheduling problems are a long-time key domain of algorithms and complexity research.  In those problems, we are generally given a finite set J of jobs with certain characteristics, and we must find a schedule for processing the jobs on one or more machines, which also may have their individual specifications. Typical characteristics of a job are its processing time, its release date, its due date, or its importance reflected by an integer weight. A significant amount of research has been devoted in the past 60 years towards designing polynomial-time algorithms which approximate the value of optimal schedules (for various objective functions). A novel approach to machine scheduling problems are multivariate algorithms, which aim to find a provably optimal schedule at the expense of an increased run time, which is permitted to depend moderately exponentially on the job characteristics or other structural parameters. We survey some recent algorithms in this paradigm, present some novel results, and discuss several challenging open problems in this exciting research area.

Prof. Jansen

Diesen Termin meinem iCal-Kalender hinzufügen