PaPaAlg
Pareto-Optimal Parameterized Algorithms
Total Cost €
0EC-Contrib. €
0Partnership
0Views
0PaPaAlg project word cloud
Explore the words cloud of the PaPaAlg project. It provides you a very rough idea of what is the project "PaPaAlg" about.
Project "PaPaAlg" data sheet
The following table provides information about the project.
| Coordinator |
UNIVERSITETET I BERGEN
Organization address contact info |
| Coordinator Country | Norway [NO] |
| Project website | https://cs.ucsb.edu/ |
| Total cost | 1˙499˙557 € |
| EC max contribution | 1˙499˙557 € (100%) |
| Programme |
1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC)) |
| Code Call | ERC-2016-STG |
| Funding Scheme | ERC-STG |
| Starting year | 2017 |
| Duration (year-month-day) | from 2017-02-01 to 2022-01-31 |
Partnership
Take a look of project's partnership.
| # | ||||
|---|---|---|---|---|
| 1 | UNIVERSITETET I BERGEN | NO (BERGEN) | coordinator | 1˙499˙557.00 |
Map
Project objective
In this project we revise the foundations of parameterized complexity, a modern multi-variate approach to algorithm design. The underlying question of every algorithmic paradigm is ``what is the best algorithm?' When the running time of algorithms is measured in terms of only one variable, it is easy to compare which one is the fastest. However, when the running time depends on more than one variable, as is the case for parameterized complexity:
**It is not clear what a ``fastest possible algorithm' really means.**
The previous formalizations of what a fastest possible parameterized algorithm means are one-dimensional, contrary to the core philosophy of parameterized complexity. These one-dimensional approaches to a multi-dimensional algorithmic paradigm unavoidably miss the most efficient algorithms, and ultimately fail to solve instances that we could have solved.
We propose the first truly multi-dimensional framework for comparing the running times of parameterized algorithms. Our new definitions are based on the notion of Pareto-optimality from economics. The new approach encompasses all existing paradigms for comparing parameterized algorithms, opens up a whole new world of research directions in parameterized complexity, and reveals new fundamental questions about parameterized problems that were considered well-understood. In this project we will develop powerful algorithmic and complexity theoretic tools to answer these research questions. The successful completion of this project will take parameterized complexity far beyond the state of the art, make parameterized algorithms more relevant for practical applications, and significantly advance adjacent subfields of theoretical computer science and mathematics.
Publications
| year | authors and title | journal | last update |
|---|---|---|---|
| 2017 |
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad and M. S. Ramanujan Onthe Parameterized Complexity of Simultaneous Deletion Problems. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2017 |
Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh and Meirav Zehavi Packing Cycles FasterThan Erdos-Pósa. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Timothy Carpenter, Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Anastasios Sidiropoulos Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2017 |
Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi Balanced JudiciousBipartition is FPT. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2017 |
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi Finding,Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Eduard Eiben, Robert Ganian, Sebastian Ordyniak A Structural Approach to Activity Selection. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi and Pavel Pudlak Beating Brute Force for(Quantified) Satisfiability of Circuits of Bounded Treewidth. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2017 |
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov and Saket Saurabh Covering vectors byspaces: Regular matroids (short version). published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2017 |
Daniel Lokshtanov, M.S. Ramanujan and Saket Saurabh A Linear-Time Parameterized Algorithmfor Node Unique Label Cover. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
David Eppstein
Daniel Lokshtanov The Parameterized Complexity of Finding Point Sets withHereditary Properties. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2019 |
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion published pages: 1-28, ISSN: 1549-6325, DOI: 10.1145/3284356 |
ACM Transactions on Algorithms 15/1 | 2019-09-09 |
| 2018 |
Daniel Lokshtanov, Dániel Marx, Saket Saurabh Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal published pages: 1-30, ISSN: 1549-6325, DOI: 10.1145/3170442 |
ACM Transactions on Algorithms 14/2 | 2019-09-09 |
| 2018 |
Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi Cliquewidth III: The OddCase of Graph Coloring Parameterized by Cliquewidth. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé and Meirav Zehavi Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2019 |
Eiben Eduard, Knop Dusan, Panolan Fahad, Suchý Ondrej Complexity of the Steiner Network Problem withRespect to the Number of Terminals published pages: , ISSN: 1868-8969, DOI: 10.4230/lipics.stacs.2019.25 |
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | 2019-09-09 |
| 2018 |
Eduard Eiben, Jonathan Gemmell, Iyad A. Kanj, Andrew Youngdahl Improved Results for Minimum Constraint Removal published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov and Amer E. Mouawad The complexity of independent set reconfigurationon bipartite graphs. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh When Recursion is Better than Iteration:A Linear-Time Algorithm for Acyclicity with Few Error Vertices. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. published pages: 2785-2800, ISSN: , DOI: 10.1137/1.9781611975031.177 |
2019-09-09 | |
| 2019 |
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs published pages: , ISSN: 0178-4617, DOI: |
Algorithmica | 2019-09-09 |
| 2019 |
Daniel Lokshtanov, Amer E. Mouawad The Complexity of Independent Set Reconfiguration on Bipartite Graphs published pages: 1-19, ISSN: 1549-6325, DOI: 10.1145/3280825 |
ACM Transactions on Algorithms 15/1 | 2019-09-09 |
| 2018 |
Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz LossyKernels for Connected Dominating Set on Sparse Graphs. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Eduard Eiben, Robert Ganian, Sebastian Ordyniak Small Resolution Proofs for QBF usingDependency Treewidth published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov, Dániel Marx, Saket Saurabh Slightly Superexponential Parameterized Problems published pages: 675-702, ISSN: 0097-5397, DOI: 10.1137/16m1104834 |
SIAM Journal on Computing 47/3 | 2019-09-09 |
| 2018 |
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov and Saket Saurabh Conflict Free Feedback Vertex Set: A Parameterized Dichotomy published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak Unary Integer LinearProgramming with Structural Restrictions published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Eduard Eiben,
Iyad A. Kanj How to Navigate Through Obstacles? published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi Quasipolynomial Representation of Transversal Matroids with Applications in ParameterizedComplexity. published pages: , ISSN: , DOI: |
2019-09-09 | |
| 2018 |
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi Erdös-Pósa Property of Obstructions to Interval Graphs. published pages: , ISSN: , DOI: |
2019-09-09 |
Are you the coordinator (or a participant) of this project? Plaese send me more information about the "PAPAALG" project.
For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.
Send me an email (fabio@fabiodisconzi.com) and I put them in your project's page as son as possible.
Thanks. And then put a link of this page into your project's website.
The information about "PAPAALG" are provided by the European Opendata Portal: CORDIS opendata.