NP-Hard problems : moderately exponential approximation and parameterized complexity

We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00874599
Author Tourniaire, Emeric
Maintainer CCSD
Last Updated May 9, 2026, 07:53 (UTC)
Created May 9, 2026, 07:53 (UTC)
Identifier NNT: 2013PA090008
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE) ; Université Paris Dauphine-PSL ; Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
creator Tourniaire, Emeric
date 2013-06-17T00:00:00
harvest_object_id ce30951c-9a5c-47af-95e2-f05cfe5afb1c
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-31T00:00:00
set_spec type:THESE