Dauphine Digital – Our Research in Performance-Guarantee Algorithmics
Algorithms Central to Data Science
As a scientific field, performance-guarantee algorithmics draws on operations research and theoretical computer science for inspiration, challenges, and motivations, and in return, provides these disciplines with new concepts and powerful tools for analysis and resolution.
Parameterized complexity
Approximate and exact resolution
Performance guarantees
Online algorithmics
Reoptimization
Combinatorial optimization
Probabilistic methods
Applications
Fundamental algorithmics is central to data science as a branch of computer science.
The field of performance-guarantee algorithmics synergizes many skills largely stemming from operations research and theoretical computer science: algorithmics, complexity theory, mathematical programming, discrete mathematics, and combinatorics.
This research field thus makes it possible to examine the resolution of difficult problems through algorithms offering performance guarantees either on the quality of calculated solutions, their execution time, or the amount of memory used.
Our Research in the University's Labs
Research studies conducted at Dauphine-PSL on these topics are developed around four main areas:
- Approximation – this has been the key field of LAMSADE members' work for many years. Work in this area is focused on both polynomial approximation (including more recent approaches like multicriteria approximation, labeled problems, and robustness) and moderately exponential (a field created by LAMSADE members) and parameterized approximation.
- Exact resolution and complexity
- Optimization models for evolutionary problems (online algorithmics, reoptimization, and probabilistic combinatorial optimization)
- Algorithmic games and combinatorial optimization
Our Researchers
Cristina Bazgan, Aristotelis Giannakos, Laurent Gourvès, Ararat Harutyunyan, Eunjung Kim, Michail Lampis, Cécile Murat, Vangelis Th. Paschos, Florian Sikora
Published Research
- Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos : Structural parameters, tight bounds, and approximation for (k, r)-center. Discrete Applied Mathematics 264 : 90-117 (2019)
- Cristina Bazgan, Florent Foucaud, Florian Sikora. Parameterized and approximation complexity of Partial VC Dimension. Theor. Comput. Sci. 766 : 1-15 (2019)
- Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora : Token Sliding on Split Graphs. STACS 2019 : 13 :1-13 :17
- Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Velcros : Exact Distance Colouring in Trees. Combinatorics, Probability & Computing 28(2) : 177-186 (2019)
- Édouard Bonnet, Vangelis Th. Paschos : Sparsification and subexponential approximation. Acta Inf. 55(1) : 1-15 (2018)
- Michael Lampis : Finer Tight Bounds for Coloring on Clique-Width. ICALP 2018 : 86 :1-86 : 14