Lower Bounds on the Running Time for Scheduling and Packing Problems

Tuesday, November 3rd, 2015, 3:30 pm–4:00 pm

Add to Calendar

iCalendar
Outlook
Google

Event:

Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms

Speaker:

Klaus Jansen, Department of Computer Science, University of Kiel

We will present several lower bounds on the running times for both exact and approximation algorithms based on the exponential time hypothesis (ETH) mainly for scheduling and packing problems (including some open problems).

Download Video [924.9MB .mp4]

Attachment	Size
Lower Bounds on the Running Time for Scheduling and Packing Problems	89.96 KB