Dagstuhl Seminar 14071: Graph modification problems
Schloss Dagstuhl, Germany
February 09-14, 2014
AMS Special Session on Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, and Its Frontiers and the Field of Incrementalization took place at the Joint Mathematics Meetings in San Diego.
([http://jointmathematicsmeetings.org/meetings/national/jmm2013/2141_program_ss28.html#title]). There were two days of excellent presentations. Anil Nerode, Mike Fellows, Annie Liu and Rod Downey gave a final summary. Frances Rosamond will write up a summary and post it here in the future. Here are slides of the excellent presentations:
Neil D. Jones.
Y. Annie Liu.
Douglas R Smith.
Moshe Y. Vardi.
Dan E. Willard.
Workshop on Kernelization (WorKer 2013)
April 10-12, 2013
Not-About-Graphs III ([http://www.cdu.edu.au/conference/csmaths])
31 July- 01 August, 2013
First Intl Conference on Creative Mathematical Sciences Communication ([http://www.cdu.edu.au/conference/csmaths])
August 2-10, 2103
Dagstuhl Seminar 12241: Data Reduction and Problem Kernels
Schloss Dagstuhl, Germany
June 10-15, 2012
6th International Symposium on Parameterized and Exact Computation (IPEC 2011),
September 7-9, 2011
AUGUST Parameterized Complexity: Not-About-Graphs Workshop followed by Problem-Solving Workshop
You are invited to Charles Darwin University in Northern Territory, Australia. Here is the Programme Description. Here is the Participants List, tentative as of 27 February. Contact Frances Rosamond at ua.ude.udc|dnomasoR.secnarF#ua.ude.udc|dnomasoR.secnarF for more information or for a letter of invitation.
DECEMBER '''IPEC 2010''': Chennai, India. Co-located with FST-TCS 2010.
AUGUST Parametrized Complexity of Computational Reasoning
Satellite workshop of MFCS and CSL. Brno, Czechia.
29 August 2010
Contact: Stefan Szeider
Only organiser’s general web site is available for the time being: http://www.szeider.net/
This workshop aims to support a fruitful exchange of ideas between the research on Parameterized Complexity on one side and the research on various forms of computational reasoning (such as Nonmonotonic, Probabilistic, and Constraint-based reasoning) on the other. Topics of interest include but are not limited to: multivariate analysis of reasoning problems, kernelization and preprocessing, fixed-parameter tractability and hardness, backdoors and decompositions.
MARCH 30 - 31
Workshop on Parameterized Complexity and Algorithm Design (2 days) at the University of Newcastle, Australia. Tuesday&Wednesday, the 30 &31st of March, held in the Engineering Quad in Building EF, Room 122. Here is the Programme. Here are the Abstracts and slides:
van der Meyer-AllIntervalSeries.mp3 van der Meyer.
There will be no fee for this Workshop. The workshop will begin on Tuesday morning 9:30 am and conclude on Wednesday afternoon. Family and children are invited to the picnic-BBQ "banquet" Tuesday evening, at the Old rail marshalling yards Pavillion at Foreshore Park. See Location 5 on this Newcastle East Heritage Walk Map.
(1) Basic Introduction to 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, Algorithms Engineering and Computational Complexity and Algorithmics.
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. gaspreise vergleich hildesheim
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).Strom Gas Preisvergleich wolfsburg
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.
RSVP to ua.ude.eltsacwen|dnomasoR.secnarF#ua.ude.eltsacwen|dnomasoR.secnarF
Sponsored by the University of Newcastle:
- Parameterized Complexity Research Unit, Office of the DVC(Research)
- Priority Research Centre for Bioinformatics, Biomarker Discovery & Information-Based Medicine
- Priority Research Centre for Computer-Assisted Research Mathematics and its Applications
APRIL "LATIN 2010" The 9th Latin American Theoretical Informatics Symposium will be held in Oaxaca, Mexico April 19-23, 2010. Submission deadline is Sept. 21, 2009. Please consult the website for full details and the call for papers.
MEMICS, Annual Doctoral Workshop on Mathematical and
Engineering Methods in Computer Science. Organized jointly by the Masaryk University
and the Brno University of Technology, Czechia. November 13 — 15 in Znojmo, Czechia.
Spring School on Fixed Parameter and Exact Algorithms, May 25-29, Ile Rousse, Corsica (France) Please consult "Call for participation" in the Table of Contents for details, or to the Webpage: [http://www-sop.inria.fr/mascotte/seminaires/AGAPE/]
'''Adaptive, Output Sensitive, Online and Parameterized Algorithms''': Dagsuhl Seminar 09171, 19.04.2009 - 24.04.2009. Organizers: Jeremy Barbay (DCC - Universidad de Chile, CL), Rolf Klein (Universitaet Bonn, DE), Alejandro Lopez-Ortiz (University of Waterloo, CA), Rolf Niedermeier (Universitaet Jena, DE).
'''Parameterized complexity and approximation algorithms''': Dagstuhl Seminar 09511, 13.12.2009 - 17.12.2009. Organizers: Erik Demaine (MIT - Cambridge, US), MohammadTaghi HajiAghayi (AT&T Research - Florham Park, US), Daniel Marx (Budapest Univ. of Technology & Economics, HU).
*ICYCS 2008 The Ninth International Conference for Young Scientists, Hunan, China. Mike Fellows is a Keynote Speaker: "How to prove W-Hardness and Why You Might Want to." Mike Langston is a Keynote Speaker: Combinatorial Analysis of High-Throughput Transcriptomic Biological Data.
Parameterized and Exact Computation • Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008.
Lecture Notes in Computer Science.
Grohe, M., Niedermeier, R. (Eds.), Vol. 5018, 2008.
Parameterized and Exact Computation • Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006. Lecture Notes in Computer Science
Bodlaender, H.L., Langston, M.A. (Eds.), Vol. 4169, 2006.
Parameterized and Exact Computation-First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Lecture Notes in Computer Science.
Dehne, Frank; Downey, Rod; Fellows, Michael (Eds.), Vol. 3162, 2004.
Proceedings. strompreisvergleich pforzheim