Dear Colleagues,
Please put Tuesday/Wednesday, the 30 and 31st of March on your calendar to
attend a *2-day** Workshop on Parameterized Complexity* at the University of
Newcastle, Australia. (Room/Building to come later).
Topics will include:
*(1) Basic Introduction* to the multivariate algorithmics, including some of
the recent achievements and open problems.
*(2) Tools and techniques* for showing FPT or hardness, such as
preprocessing and kernelization, iterative compression, and reductions.
*(3) Applications* to important fields such as Artificial Intelligence,
Social Choice, Bioinformatics, Machine Learning, and Computational
Complexity and Algorithmics.
Speakers so far include Mike Fellows and Fran Rosamond (Newcastle), Vlad
Estivill-Castro (Griffith), Toby Walsh (NICTA/UNSW), Nina Naroditskaya
(NICTA), Danny Hermelin (Max Planck Institute, Saarbrucken), among others.
*Parameterized Complexity* is the rapidly advancing field of multivariate
algorithmics with wide applications in almost every field dealing with
algorithms. The basic idea is that not all parts of a problem input are
created equal, and many instances of NP-complete problems are actually
tractable, with practical algorithms, when various parts (parameters) of the
input structure can be bounded. See
*http://fpt.wikidot.com<https://groupwise-web.newcastle.edu.au/webaccess/webacc?User.context=819eca76b2d86da0a559cc963da9aea74b56121&merge=linkurl&Url.linkText=http%3a%2f%2ffpt%2ewikidot%2ecom>
*, or
http://www.newcastle.edu.au/institute/parameterized-complexity-research-unit/
As an example in *multi-agent systems*, coalitions enable agents to achieve
goals while sharing resources. Most coalitional games problems are NP-hard,
but FPT (Fixed-Parameter Tractable) in the number of goals, implying that if
the number of goals is bounded then an efficient algorithm is available.
Similarly, the problems are FPT in the combination of the number of agents
and resources, again implying that if these parameters are bounded then an
efficient algorithm is available. On the other hand, the problems are
para-NP hard in the number of resources, implying that even if we bound the
number of resources the problems (probably) remain hard (Shrot, Aumann,
Kraus, AAMAS 2009).
As an example in *bioinformatics* (motif search in strings) and *coding
theory* (minimum radius), the NP-hard CLOSEST STRING problem is to find a
length-L string that minimizes the maximum Hamming distance d to a given set
of k length-L strings. This is FPT parameterized by the combination
(alphabet size, k), and also d.
As an example in* graphs*, VERTEX COVER is FPT parameterized by the size of
the cover, but DOMINATING SET remains hard.
There will be no fee for this Workshop. The workshop will begin on Tuesday
morning 9:30 am and conclude on Wednesday afternoon. There will be a picnic
banquet Tuesday evening, family and children are invited.
Kindly circulate this invitation to Faculty, Students, Visiting Scholars,
Research Visitors, and all who may be interested.
RSVP to *Frances.Rosamond@newcastle.edu.au*
Frances Rosamond, Ph.D.
Parameterized Complexity Research Unit
The Office of DVC(Research)
The University of Newcastle
NSW, Australia 2308
Ph +61-2-4921-5441
Fax +61-2-4921-7052
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
