Title	A brief introduction to kernelization
Creator	Kratsch, Stefan
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2015-12-01T09:12
Description	Kernelization is a notion from parameterized complexity that captures the concept of efficient preprocessing for NP-hard problems. A kernelization is a polynomial-time algorithm that given an instance (x; k) with parameter k will return an equivalent instance of size bounded only in terms of k. In particular, we are interested in polynomial kernels where the bound depends polynomially on k. The talk will give an introduction to core concepts from kernelization. Where appropriate, relations to approximability of the considered problems will be discussed
Extent	55 minutes
Subject	Mathematics; Computer science; Combinatorics; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Bonn
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2016-06-01
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0303481
URI	http://hdl.handle.net/2429/58215
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