Title	Lower bounds on the running time for packing and scheduling problems
Creator	Jansen, Klaus
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2015-12-02T09:32
Description	We will present lower bounds on the running time for both exact and approximation algorithms based on the exponential time hypothesis (ETH). First, we will discuss lower and upper bounds on the running time for exact algorithms for subset sum, partition, knapsack, bin packing, and scheduling on identical machines. Next we give lower bounds on the running time of approximation schemes for the multiple knapsack, multi-dimensional knapsack and scheduling problem on identical, uniform, and unrelated machines. This is joint work with Lin Chen, Felix Land, Kati Land, and Guochuan Zhang.
Extent	26 minutes
Subject	Mathematics; Computer science; Combinatorics; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Kiel
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2016-06-07
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0304577
URI	http://hdl.handle.net/2429/58238
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos