Opendata, web and dolomites


Technology transfer between modern algorithmic paradigms

Total Cost €


EC-Contrib. €






Project "TOTAL" data sheet

The following table provides information about the project.


Organization address
postcode: 00 927

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 Poland [PL]
 Project website
 Total cost 1˙417˙625 €
 EC max contribution 1˙417˙625 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2015-STG
 Funding Scheme ERC-STG
 Starting year 2016
 Duration (year-month-day) from 2016-04-01   to  2021-03-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    UNIWERSYTET WARSZAWSKI PL (WARSZAWA) coordinator 1˙417˙625.00


 Project objective

The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by now developed, they have grown mostly on their own. In our opinion the two fields have critical mass allowing for synergy effects to appear when using techniques from one area to obtain results in the other, which is the main theme of the project. Furthermore, practical effectiveness of randomized local search heuristics is a not yet understood phenomenon. We believe that substantial increase of our understanding of superpolynomial running times in recent years should allow for rigorous proofs of parameterized and approximation results obtained by those methods. Based on our experience with parameterized complexity and approximation algorithms we propose three research directions with potential of solving major long-standing open problems in both areas with the following objectives. (a) Transfer from Approximation to FPT: use the PCP theorem to prove lower bounds for exact parameterized algorithms under the Exponential Time Hypothesis and take advantage of extended formulations in FPT branching algorithms. (b) Transfer from FPT to Approximation: utilize parameterized algorithms tools in local-search-based approximation algorithms and explore the potential of proving new inapproximability results based on the Exponential Time Hypothesis. (c) Rigorous Analysis of Practical Heuristics: unravel the practical effectiveness of randomized local search heuristics by proving their parameterized and approximation properties, when given subexponential or even moderately exponential running time. Our objectives lie in the frontier of fixed parameter tractability and approximation areas. Complete resolution of our goals would dramatically change our understanding of both areas, with further consequences in other disciplines within computer science.


year authors and title journal last update
List of publications.
2017 Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
Approximation and Parameterized Complexity of Minimax Approval Voting
published pages: 459--465, ISSN: , DOI:
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence 2020-04-23
2017 Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
published pages: , ISSN: , DOI:
Proceedings of FOCS 2017 5 2020-04-23

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "TOTAL" 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 ( 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 "TOTAL" are provided by the European Opendata Portal: CORDIS opendata.

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


The Mass Politics of Disintegration

Read More  

Photopharm (2020)

Photopharmacology: From Academia toward the Clinic.

Read More  


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

Read More