The S-EX-AP-PE-AL Project
Project Summary
Because the vast majority of interesting optimization problems are NP-hard, dealing with NP-hardness is a central question of theoretical computer science. The two most well-studied approaches either consider polynomial-time approximation algorithms, or exact algorithms running in (sub-)exponential or FPT time.
The goal of this project is to unify these two approaches into a coherent theory of sub-exponential and parameterized approximation. Such a theory will furnish the tools to determine the best approximation ratio achievable for a problem for any given amount of time (not just polynomial time), or conversely, the precise amount of time needed to obtain any desired approximation ratio.
We aim to develop novel techniques to answer such questions, building on preliminary results by our team indicating this direction's feasibility, but also its promise for applications, as many problems admit in sub-exponential time algorithms with vastly improved approximation guarantees.
The S-EX-AP-PE-AL project is a research project funded by the French National Research Agency (ANR) under the young researcher program (JCJC). The project is headed by Michael Lampis and carried out mainly by a research team based in LAMSADE, Université Paris-Dauphine, with external collaborators at IRIF, Université de Paris, and Charles University in Prague. .
Specifics
| ANR JCJC project | S-EX-AP-PE-AL (ANR-21-CE48-0022) |
|---|---|
| Full Title | Sub-EXponential APproximation and ParametErized ALgorithms |
| Principal Investigator | Michael Lampis |
| Starting Date | 01/02/2022 (48 months) |
| Budget | 177.400€ |
| Host Institute | LAMSADE (CNRS / Université Paris-Dauphine) |