2019
AUGUST 2019
BUILDING BRIDGES BETWEEN PARAMETERIZED COMPLEXITY & PRACTICAL COMPUTING (PCPC) August 5—9, 2019 in Bergen, Norway
WEBSITE: https://www.uib.no/en/rg/algo/127995/parameterized-complexity-and-practical-computing-workshop
KEYNOTE SPEAKERS AND THEIR APPLICATION AREAS:
•Prof. Gregory Gutin (Royal Holloway, University of London) - Di-graphs, Computer Security-Cryptography, Workflow Satisfiability.
•Prof. Klaus Jansen (University of Kiel, Germany) - Scheduling problems
•Prof. Blair Sullivan (Univ Utah, Oak Ridge National Lab USA) -Data-driven science: Computational neuroscience, computational biology (genomics), quantum computing, social networks. biomechanical engineering.
LOCATION AND DATES:
The workshop will take place in Bergen, Norway during the week starting Monday 05 August, 2019.
Days 1 & 2 (Monday and Tuesday, 05 and 06 August) will be held at the Solstrand Hotel.
Day 3 (Wednesday 07 August) will include a fjord trip offering the opportunity for continued discussion. See below.
Days 4 & 5 (Thursday and Friday, 08 and 09) talks will be presented at the University of Bergen.
SUBMISSIONS:
The workshop aims to bring together researchers and practitioners of Parameterized algorithms to share their perspectives and experiences. We solicit presentations describing research results with practical applications, and position statements leading to new directions, standpoints, and learned lessons. There will be long (40 min) and short (20 min) talks and discussion time. Exact format TBA.
REGISTRATION & ABSTRACTS:
To REGISTER or to SUBMIT an abstract together with your preference for length of talking time, send an email to Mateus De Oliveira Oliveira <on.biu|arievilO.suetaM#on.biu|arievilO.suetaM>. In the Subject line put the words: PCPC REGISTRATION.
There is no fee for the workshop.
The following expenses will be covered by Mike Fellows' Norwegian Toppforsk Grant:
• Accommodation to all participants for one night (August 05 to August 06) at the Solstrand Hotel. Meals are provided at the hotel.
• Buses from UiB to the workshop venue on the morning of August 05 and back to UiB on the evening of August 06.
• Taxis from the airport to Solstrand Hotel for people arriving at Bergen airport on the morning of August 05. If you are contemplating this possibility please make taxi arrangements through the hotel so that the hotel can arrange joint taxi if suitable.
• Fjord trip outing on Wednesday to continue discussions.
Fjord Trip on Wednesday, Day 3
There will be a cruise trip to the fjords on Wednesday, 07 July. The cruise will pass through deep fjords, steep mountains, mighty waterfalls, and powerful currents. The duration of the trip is about 3 hours. The cruise is called Fjordcruise Bergen-Mostraumen. The departure is from Zachariasbryggen quay at the Fish Market in Bergen. Boarding time to be announced.
FOR MORE INFORMATION CONTACT: on.biu|dnomasor.secnarF#on.biu|dnomasor.secnarF, on.biu|swollef.leahciM#on.biu|swollef.leahciM
JULY 2019
The 2nd edition of the Parameterized Approximation Algorithms Workshop (PAAW) will take place as a satellite workshop of ICALP 2019 in Patras, Greece, on Monday July 8th 2019.
https://sites.google.com/site/aefeldmann/parameterized-approximation-algorithms-workshop-paaw-2019
Two standard approaches to handle hard (typically NP-hard) optimization problems are to develop approximation and parameterized algorithms. For the former, the runtime should be polynomial in the input size, but the computed solution may deviate from the optimum. For the latter, the optimum solution should be computed, but any super-polynomial runtime should be isolated to some parameter of the input. Some problems however are hard to approximate on one hand, and on the other it is also hard to obtain parameterized algorithms for some given parameter. In this case one may still hope to obtain parameterized approximation algorithms, which combine the two paradigms, i.e. the computed solution may deviate from the optimum and the runtime should have super-polynomial dependence only in some given parameter. Recently there has been a great deal of development in proving the existence or non-existence of parameterized approximation algorithms, and the aim of this workshop is to bring together active researchers of this emerging field, so that they may share their results and insights.
Topics of interest
- Parameterized approximation algorithms
- Lossy kernelization
- Parameterized inapproximability
- Fine-grained complexity of approximation
- Subexponential time approximation
- Efficient polynomial-time approximation schemes
Contributed talks: If you would like to contribute a talk at this workshop, please send an email with subject "PAAW talk" to "feldmann.a.eatgmail.com" containing the title and an abstract, no later than Friday April 26th. Both talks on already published as well as yet unpublished results on the above listed topics are welcome. There will not be any published proceedings for this workshop.
Important dates
Submission deadline: Friday April 26th, 2019
Notification: Friday May 17th, 2019
Early registration deadline: Thursday May 30, 2019
Workshop: Monday July 8th, 2019
Registration: To participate please register through the ICALP registration page.
MARCH 2019
March 3rd, 2019 - March 8th, 2019
Parameterized graph algorithms & data reduction: Theory meets practice
Organized at Shonan Village in Japan
Organizers
Bart M. P. Jansen - TU Eindhoven
Christian Schulz - University of Vienna
Hisao Tamaki - Meiji University
2018
SEPTEMBER 2018
September 10th, 2018 - September 14th, 2018
NWO-JSPS joint seminar "Computations on Networks with a Tree-Structure: From Theory to Practice"
Sponsored by NWO, JSPS, NETWORKS and Eurandom
Dynamic programming based on tree decomposition is one of the most successful approaches for solving important hard problems on networks, with problems ranging from several application areas (including operations research, computational biology, etc.). In theory, Bodlaender's algorithm and Courcelle's theorem give for a large collection of problems algorithms that solve them in time linear in the number of vertices, assuming we have a graph or network with the appropriate structure (i.e., the treewidth is bounded); a condition that appears to be true for many networks from quite various applications. However, while these results and the corresponding algorithms play a central role in many theoretical / foundational studies, and are seen as cornerstones in the field of parameterized algorithms ("fixed parameter tractability"), the direct practical use is under debate: while asymptotic optimal, the constant factors hidden in the big-Oh notation are huge. Thus, a worthy topic of study is to see how the theoretical results can be moved to useful practical results. This asks for the development of new algorithmic insights and algorithm engineering studies, alongside with further insights in the structure of networks that allow these type of dynamic programming algorithms. Both Japan and the Netherlands have strong and well known researchers in this area. This seminar brings together these experts to initiate new studies towards significant progress both in practice as in theory.
Organizers
Hans Bodlaender University of Utrecht / TU Eindhoven
Bart Jansen TU Eindhoven
Erik Jan van Leeuwen University of Utrecht
Jesper Nederhof TU Eindhoven
Yota Otachi Kumamoto University
Tom van der Zanden University of Utrecht
For more information on speakers etc., please visit the Eurandom website
JULY 2018
The Parameterized Approximation Algorithms Workshop (PAAW) will take place
as a satellite workshop of ICALP 2018 in Prague, Czechia, on Monday July
9th 2018.
https://sites.google.com/site/aefeldmann/workshop
Two standard approaches to handle hard (typically NP-hard) optimization
problems are to develop approximation and parameterized algorithms. For the
former, the runtime should be polynomial in the input size, but the
computed solution may deviate from the optimum. For the latter, the optimum
solution should be computed, but any super-polynomial runtime should be
isolated to some parameter of the input. Some problems however are hard to
approximate on one hand, and on the other it is also hard to obtain
parameterized algorithms for some given parameter. In this case one may
still hope to obtain parameterized approximation algorithms, which combine
the two paradigms, i.e. the computed solution may deviate from the optimum
and the runtime should have super-polynomial dependence only in some given
parameter. Recently there has been a great deal of development in proving
the existence or non-existence of parameterized approximation algorithms,
and the aim of this workshop is to bring together active researchers of
this emerging field, so that they may share their results and insights.
Topics of interest
- Parameterized approximation algorithms
- Lossy kernelization
- Parameterized inapproximability
- Fine-grained complexity of approximation
- Efficient polynomial-time approximation schemes
Contributed talks: If you would like to contribute a talk at this workshop, please send an email with subject "PAAW talk" to "feldmann.a.eatgmail.com" containing the title and an abstract, no later than Friday April 20th. Both talks on already published as well as yet unpublished results on the above listed
topics are welcome. There will not be any published proceedings for this workshop.
Important dates
Submission deadline: Friday April 20th, 2018
Notification: Friday May 18th, 2018
Early registration deadline: Thursday May 31, 2018
Workshop: Monday July 9th, 2018
Registration:To participate please register through the ICALP registration page.
2017
JUNEJULYAUGUST 2017
There is a lot happening in Australia this summer:
1. Computational & Algorithmic Topology Workshop (CATS), The Univ of Sydney, 27 June – 1 July 2017. Serge Gaspers will give an introductory lecture on parameterized complexity.
2. Computational Geometry Week (CG Week 2017), the premier international forum for advances in computational geometry and its many applications. Univ of Queensland, Brisbane, July 4—7. Benjamin Burton, local organizer.
3. The 28th International Workshop on Combinatorial Algorithms (IWOCA2017), Newcastle, July 17–-21. Special memorial to Mirka Miller.
4. The big IJCAI / SAT / CP / ICLP event in Melbourne, August 19—25.
SEPTEMBER 2017
PARAMETERIZED COMPLEXITY SUMMER SCHOOL The 3rd Parameterized Complexity Summer School will be held in Vienna, Austria, from 1 to 3 September 2017 (Friday-Sunday) co-located with ALGO 2017 and will take place in the same venue. See https://algo2017.ac.tuwien.ac.at/pcss/
PACE announcements at IPEC.
IPEC 2017 Vienna, Austria 4—8 September 2017.
Excellent Student Paper Award eligibility: at most one author has received a PhD degree before the paper submission deadline. The students' contributions must be substantial, and a student must give the presentation at the conference. IMPORTANT Please identify if you are submitting a Student Paper. There will also be Best Paper Award (not necessarily student).
DECEMBER 2017
Recent Advances in Parameterized Complexity (rapctelaviv.weebly.com). The event will be held on December 3-7, 2017, at Tel Aviv, Israel.
The purpose of Recent Advances in Parameterized Complexity is twofold. First, the event would present an overview of several recent, exciting advances in the field of Parameterized Complexity. Second, to attract new researchers to work on topics in this field of research, the program would also consist of a preparatory school at the level of an introductory course. We thus invite both graduate students and established researchers to participate in Recent Advances in Parameterized Complexity. For more details, see rapctelaviv.weebly.com.
2016
DECEMBER
Sydney Algorithms Workshop 2016 on parameterized complexity and computational geometry, 6-9 December 2016.
JUNE
The 8th Intl Conf on Fun with Algorithms (FUN 2016) will be held in La Maddalena, Maddalena Islands, Italy, on June 8 – 10, 2016. More information at http://www2.idsia.ch/cms/fun16/
Sooner or later society will realise that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else. D. E. Knuth
MARCH
Dear colleagues, We are glad to invite you to the ELC School on Parameterized Algorithms which will be held in Osaka, Japan, from March 17th until Sunday 20th, 2016. The lectures will cover introductory notions, accessible to beginners, as well as more recent and advanced results. The school is primarily intended for graduate students and young researchers who wish to get acquainted with and further their knowledge of
this rapidly growing field.
Lecturers:
- Daniel Lokshtanov, University of Bergen, Norway,
- Michal Pilipczuk, University of Warsaw, Poland.
You can find more information at
http://www.al.ics.saitama-u.ac.jp/elc/blog/elc-school-on-parameterized, or contact us at moc.liamg|etnomlebymer#moc.liamg|etnomlebymer with any question you may have.
We hope you will be able to accept this invitation and attend the school, and are looking forward to seeing you in Osaka!
Best regards,
Local organizers: Rémy Belmonte and Naoki Katoh
2015
NOVEMBER
Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms (ETH workshop)
Berkeley, California
November 2–6, 2015
JULY
The 9th International Frontiers of Algorithmics Workshop (FAW 2015)
Guilin, Guangxi, China.
July 3-5, 2015
JUNE
Workshop on Kernels (WorKer 2015)
Nordfjordeid, Norway
June 1-4, 2015
MAY
The 2nd Workshop on Exploring Beyond the Worst Case in Computational Social Choice (EXPLORE 2015)
Istanbul, Turkey
May 4, 2015
MARCH
Special session on Parameterized Complexity at the 2015 Annual North American meeting of the Association for Symbolic Logic (ASL 2015)
University of Illinois at Urbana-Champaign, Illinois, USA
March 25-28, 2015
2014
DECEMBER 8
FPT New Ideas Workshop led by Mike Fellows and Saket Saraubh, Dec 8, IMSC, Chennai.
DECEMBER 9 through 12
Creative Mathematical Sciences Communication (CMSC), the Second International CMSC, Dec 9 through 12, IMSC, Chennai.
Co-organizers are R. Ramanujam (Jam), ni.csmi.ser|maj#ni.csmi.ser|maj and Frances Rosamond, ua.ude.udc|dnomasoR.secnarF#ua.ude.udc|dnomasoR.secnarF.
We invite you to a gathering of creative mathematicians and theoretical computer scientists and playwriters and actress and artists and dancers and educators who are exploring new ways of communicating mathematics to children of all ages.
WEBSITE: http://www.imsc.res.in/~jam/cmsc/register.html Register on the website or contact the co-organizers.
Featured are keynote talks by researchers and communicators with original experience in popularizing mathematics. We are equally interested in how outreach contributes to serious mathematical sciences research. We are also interested in how to include stories and both-ways thinking so that learners traditionally disenfranchised from maths can become involved.
The conference explores new ways of thinking initiated by COMPUTER SCIENCE UNPLUGGED! and similar efforts (www.csunplugged.org). We will investigate creating new activities, with 21st Century computational and both-ways thinking.
The conference series was started in Darwin, 2013 (www.cdu.edu.au/conference/csmaths)
Participation in the conference is open to everyone and will be limited only by logistical constraints.
OCTOBER
Workshop on Challenges in Algorithmic Social Choice (CASC 2014)
Eisenhardt Castle, Bad Belzig (near Berlin), Germany
October 8-11, 2014
JULY
2nd Workshop on the Parameterized Complexity of Computational Reasoning (PCCR 2014),
Report on PCCR 2014, including open problems.
Vienna, Austria
July 17-18, 2014
part of the Vienna Summer of Logic 2014
MAY
The 1st Workshop on Exploring Beyond the Worst Case in Computational Social Choice (EXPLORE 2014)
Paris, France
May 6, 2014
FEBRUARY
Dagstuhl Seminar 14071: Graph modification problems
Schloss Dagstuhl, Germany
February 09-14, 2014
2013
JANUARY
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:
V. Arvind.
Holger Dell.
Rod Downey.
Andrew Drucker.
Petr Hlineny.
Neil D. Jones.
Yiannis Koutis.
Y. Annie Liu.
Rolf Niedermeier.
Douglas R Smith.
Ulrike Stege.
Moshe Y. Vardi.
Dan E. Willard.
Ryan Williams.
APRIL
Workshop on Kernelization (WorKer 2013)
Warsaw, Poland
April 10-12, 2013
JULY
International Workshop on Approximation, Parameterized and EXact algorithms (APEX 2013),
Riga, Latvia
July 6-7, 2013
co-located with ICALP 2013
August
Not-About-Graphs III ([http://www.cdu.edu.au/conference/csmaths])
Darwin, Australia
31 July- 01 August, 2013
First Intl Conference on Creative Mathematical Sciences Communication ([http://www.cdu.edu.au/conference/csmaths])
Darwin, Australia
August 2-10, 2103
2012
SEPTEMBER
7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
Ljubljana, Slovenia
September 12-14, 2012
part of ALGO 2012
JULY
Workshop on Applications of Parameterized Algorithms and Complexity (APAC 2012) at ICALP 2012,
Warwick, UK
July 8, 2012
JUNE
Dagstuhl Seminar 12241: Data Reduction and Problem Kernels
Schloss Dagstuhl, Germany
June 10-15, 2012
FEBRUARY
International Workshop on Approximation, Parameterized and EXact algorithms (APEX 2012),
Paris, France
February 28-29, 2012
co-located with STACS 2012
Parameterized Complexity Tutorial at CATS 2012
Melbourne, Australia
February 3, 2012
2011
SEPTEMBER
6th International Symposium on Parameterized and Exact Computation (IPEC 2011),
Saarbrücken, Germany
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.
2010
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:
Brankovic.
EstivillCastro.
Heednacram.
Hermelin.
McCartin.
Mathieson.
Narodytska.
Parsa.
Renz.
Rosamond.
Walsh.
van der Meyer-AllIntervalSeries.mp3 van der Meyer.
A general report on the workshop is Report2010.pdf here. Here is Newcastle Herald article about the workshop.
Directions to Newcastle can be found here. Here is Campus Map.
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.
Topics included:
(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.
2009
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/]
"IWPEC 2009": Copenhagen, Denmark will be co-located with EATCS, the 16th Annual European Symposium on Algorithms (ESA). Guest speakers will be Noga Alon and Hans Bodlaender.
'''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).
2008
*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.
Proceedings.
2006
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.
[http://www.springer.com/computer/foun
dations/book/978-3-540-39098-5 Proceedings].
2004
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