Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Coupe maximum). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Glorieux, Antoine. Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe.

Degree: Docteur es, Mathématiques, 2017, Evry, Institut national des télécommunications

Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial

The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with…

Advisors/Committee Members: Ben Ameur, Walid (thesis director).

Subjects/Keywords: Graphe; Orientation; Optimisation combinatoire; Complexité; NP-complet; NP-dur; Algorithme d'approximation; Coupe maximum; Programmation linéaire mixte; Optimisation semi-définie positive; Graph; Orientation; Combinatorial optimization; Complexity; NP-complete; NP-hard; Approximation algorithm; Maximum cut; Mixed integer programming; Semidefinite programming

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Glorieux, A. (2017). Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe. (Doctoral Dissertation). Evry, Institut national des télécommunications. Retrieved from http://www.theses.fr/2017TELE0011

Chicago Manual of Style (16th Edition):

Glorieux, Antoine. “Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe.” 2017. Doctoral Dissertation, Evry, Institut national des télécommunications. Accessed November 20, 2019. http://www.theses.fr/2017TELE0011.

MLA Handbook (7th Edition):

Glorieux, Antoine. “Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe.” 2017. Web. 20 Nov 2019.

Vancouver:

Glorieux A. Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe. [Internet] [Doctoral dissertation]. Evry, Institut national des télécommunications; 2017. [cited 2019 Nov 20]. Available from: http://www.theses.fr/2017TELE0011.

Council of Science Editors:

Glorieux A. Optimizing the imbalances in a graph : Optimiser les déséquilibres dans un graphe. [Doctoral Dissertation]. Evry, Institut national des télécommunications; 2017. Available from: http://www.theses.fr/2017TELE0011

.