Opendata, web and dolomites


Novel Algorithmic Techniques through the Lens of Combinatorics

Total Cost €


EC-Contrib. €






Project "ALGOCom" data sheet

The following table provides information about the project.


Organization address
address: OTAKAARI 1
city: ESPOO
postcode: 2150

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 Finland [FI]
 Total cost 1˙411˙258 €
 EC max contribution 1˙411˙258 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2017-STG
 Funding Scheme ERC-STG
 Starting year 2018
 Duration (year-month-day) from 2018-02-01   to  2023-01-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    AALTO KORKEAKOULUSAATIO SR FI (ESPOO) coordinator 1˙411˙258.00


 Project objective

Real-world optimization problems pose major challenges to algorithmic research. For instance, (i) many important problems are believed to be intractable (i.e. NP-hard) and (ii) with the growth of data size, modern applications often require a decision making under {em incomplete and dynamically changing input data}. After several decades of research, central problems in these domains have remained poorly understood (e.g. Is there an asymptotically most efficient binary search trees?) Existing algorithmic techniques either reach their limitation or are inherently tailored to special cases.

This project attempts to untangle this gap in the state of the art and seeks new interplay across multiple areas of algorithms, such as approximation algorithms, online algorithms, fixed-parameter tractable (FPT) algorithms, exponential time algorithms, and data structures. We propose new directions from the {em structural perspectives} that connect the aforementioned algorithmic problems to basic questions in combinatorics. Our approaches fall into one of the three broad schemes: (i) new structural theory, (ii) intermediate problems, and (iii) transfer of techniques. These directions partially build on the PI's successes in resolving more than ten classical problems in this context.

Resolving the proposed problems will likely revolutionize our understanding about algorithms and data structures and potentially unify techniques in multiple algorithmic regimes. Any progress is, in fact, already a significant contribution to the algorithms community. We suggest concrete intermediate goals that are of independent interest and have lower risks, so they are suitable for Ph.D students.


year authors and title journal last update
List of publications.
2019 Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
published pages: , ISSN: , DOI:
Symposium on Theory of Computing (STOC) 2019-10-08
2018 Chalermsook, Parinya; Das, Syamantak; Even, Guy; Laekhanukit, Bundit; Vaz, Daniel
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
published pages: , ISSN: , DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.8
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 5 2019-10-03
2018 Chalermsook, P.; Goswami, M.; Kozma, L.; Mehlhorn, K.; Saranurak, T.
Multi-Finger Binary Search Trees
published pages: , ISSN: , DOI: 10.4230/LIPIcs.ISAAC.2018.55
International Symposium on Algorithms and Computation 5 2019-10-03
2019 Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-Time Approximation
published pages: 3993-4009, ISSN: 0178-4617, DOI: 10.1007/s00453-018-0512-8
Algorithmica 81/10 2019-10-03
2018 Timothy Chan, Thomas van Dijk, Krzysztof Fleszar, Joachim Spoerhase, Alexander Wolff
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity
published pages: , ISSN: , DOI:
International Symposium on Algorithms and Computation 2019-10-03
2019 Vishwas Bhargava, Markus Blaser, Gorav Jindal, Anurag Pandey
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials
published pages: , ISSN: , DOI:
ACM-SIAM Symposium on Discrete Algorithms 2019-10-03
2019 Chalermsook, Parinya; Schmid, Andreas; Uniyal, Sumedha
A Tight Extremal Bound on the Lov\'{a}sz Cactus Number in Planar Graphs
published pages: , ISSN: , DOI: 10.4230/LIPIcs.STACS.2019.19
International Symposium on Theoretical Aspects of Computer Science (STACS) 5 2019-10-03
2019 Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, Sumedha Uniyal
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
published pages: , ISSN: , DOI:
International Colloquium on Automata, Languages, and Programming 2019-10-03

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

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

SUExp (2018)

Strategic Uncertainty: An Experimental Investigation

Read More  

SPA4AstroQIT (2019)

Broadband Quantum-Limited Parametric Amplifier for Astronomy and Quantum Information Technology

Read More  

MIMATOM (2020)

Paleomagnetism and rock-magnetism by Micro-Magnetic Tomography

Read More