Multivariate Analysis - Parameterized Complexity
CATS Tutorial on FRIDAY 3
February (Last day of ASCW Week)
This CATS tutorial offers a basic introduction
to parameterized complexity theory,
parameterized algorithms and applications. The multivariate
perspective on complexity analysis and algorithm design has expanded rapidly in
recent years, and has applications all across Computer Science where there are
NP-hard problems. There will be examples
across many fields; such as, massive parallel processing of huge data sets,
computational biology, computational vision, AI, and computational social
choice. There will be Open Problems for
good thesis projects. In addition to the basics, recent developments, such as
lower bound techniques for FPT kernelization will be discussed. The parameterized complexity research
community is strongly interdisciplinary, with great promise for further
interdisciplinary opportunities. We look
forward to welcoming many researchers/students to the Tutorial.
Multivariate
complexity analysis
considers the effect on problem complexity of secondary measurements beyond
the overall input size n. The central notion of fixed
parameter tractability is a generalization of
polynomial time based on confining any non-polynomial (typically exponential)
complexity costs to a function only of these secondary measurements. Parameterized algorithms have strong
connections to heuristics for NP-hard problems, and the multivariate approach
allows more realistic modeling of real-world input distributions. Take for example the data cleaning problem: We have n data samples from some physical
experiment. Due to measurement errors some data points make no sense. To be
more precise: there can be pairs of data points that contradict each other.
The goal is to delete as few data points as possible to get rid of all
conflicts. As a parameterized problem we can state this as follows: The input
consists of n data points and a
number k the parameter. The
question is whether we can delete up to
k data points to make the data consistent. In practice n
can be very big, but we expect k to
be much smaller. This problem is NP-complete, but we can easily find an
algorithm that runs in time O(2^{k} + n). ABOUT THE FIELD The Parameterized
Complexity Newsletter
is archived at http://fpt.wikidot.com. The newsletter and the wiki give history
and recent developments and should be consulted for background material for
the tutorial. Recent conference
papers and papers on arXiv are located on the wiki. The field has generated well over 10 million Euros in
research funding in the past two years, including an ARC Discovery Early Career Researcher Award, ARC-PF, two Starting Grants and one Advanced Grant from the European
Research Council, the President of
Ireland Young Researcher Award of more than half a million Euro over a
four year period, two Large Norwegian grants, US Office of Naval Research, NSF, Google Faculty Research, amongst other awards. At SODA 2011 there were nine papers concerning
parameterized complexity & algorithms. TUTORIAL ORGANIZER Any
questions, please contact Frances Rosamond Email:
frances.rosamond@cdu.edu.au Phone:
61-0402-47-3323 |
SCHEDULE New PRESENTERS Michael Fellows, Charles Darwin Univ., Au Franz
Brandenburg,
Univ. Passau, Germany Ljiljana
Brankovic,
Univ. Newcastle, Au Michael Langston, Univ. Tennessee and Oak Ridge
National Laboratory, USA Gabor Erdelyi, Univ. Siegen, Germany TOPICS 1.
Introduction and basic definitions * Why parameterized complexity? * The "art of parameterization" * Parameterized complexity classes * Exponential time hypothesis * Parameterized reductions 2. FPT
algorithm design * Bounded search trees * Greedy localization * Color coding * Tree and path decompositions * Graph minors and wqo's * Courcelle's theorem * Kernelization * Iterative compression Cost: FREE to students. Just show up on the day. Venue: The Tutorial is part of the ACSW Week and CATS, and will be held in Melbourne at RMIT. The Friday events (CATS tutorial, 2 ACE workshops) will take place in the Storey Hall seminar rooms (aka the same place as the rest of the conference). I can't tell you exactly which such room until mid-January or so, but this narrows it down to within a few metres at most. |
Go to ACSW Week
Go to CATS website
Go to Parameterized Complexity WIKI