Opendata, web and dolomites

PaPaAlg

Pareto-Optimal Parameterized Algorithms

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

Project "PaPaAlg" data sheet

The following table provides information about the project.

Coordinator
UNIVERSITETET I BERGEN 

Organization address
address: MUSEPLASSEN 1
city: BERGEN
postcode: 5020
website: www.uib.no

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 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.

# participants  country  role  EC contrib. [€] 
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
List of publications.
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.

More projects from the same programme (H2020-EU.1.1.)

VictPart (2019)

Righting Victim Participation in Transitional Justice

Read More  

DISINTEGRATION (2019)

The Mass Politics of Disintegration

Read More  

PROGRESS (2019)

The Enemy of the Good: Towards a Theory of Moral Progress

Read More