thesis

Aspects Combinatoires et Analytiques de Problèmes d'Optimisation Difficiles : les Coupes Maximales

Defense date:

Jan. 1, 2012

Edit

Institution:

Paris 13

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

We present an analytical approach of the max-2-xorsat and max-cut optimization problems by means of enumerative and analytic combinatorics. In this work, we study the generating functions of optimal configurations of these problems. Combining these tools with complex analysis, we then quantify the maximum number of satisfiable clauses of max-2-xorsat random formulas and the max-cut of sparse random graphs.

Abstract FR:

Nous présentons une approche analytique des problèmes d'optimisations MAX-2-XORSAT et MAX-CUT basée sur la combinatoire énumérative et analytique. Dans cette thèse, nous étudions les séries génératrices liées aux configurations optimales de ces problèmes. En combinant ces outils avec ceux d'analyse complexe, nous quantifions alors le nombre maximum de clauses satisfaisables des instances aléatoires de MAX-2-XORSAT et le MAX-CUT des graphes aléatoires peu denses.