Show simple item record

NP-Hard problems : moderately exponential approximation and parameterized complexity

dc.contributor.advisorPaschos, Vangelis
hal.structure.identifier
dc.contributor.authorTourniaire, Emeric*
dc.date.accessioned2013-11-14T17:26:35Z
dc.date.available2013-11-14T17:26:35Z
dc.date.issued2013-06
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12071
dc.description.abstractfrNous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.en
dc.language.isofren
dc.subjectOptimisation combinatoireen
dc.subjectAlgorithmes d'approximationen
dc.subjectThéorie des graphesen
dc.subjectComplexitéen
dc.subjectApproximationen
dc.subject.ddc003en
dc.titleProblèmes NP-difficiles : approximation modérément exponentielle et complexité paramétriquefr
dc.titleNP-Hard problems : moderately exponential approximation and parameterized complexityen
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenWe 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.en
dc.identifier.citationpages129en
dc.identifier.theseid2013PA090008en
dc.subject.ddclabelRecherche opérationnelleen
dc.rights.intranetnonen
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record