2023

Heure:	16:00 - 17:00
Lieu:	https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn - code: 514019
Résumé:	Hamiltonian degree condition for tough graphs
Description:	Cleophee Robin A graph G is hamiltonian if there exists a G cycle containing all G vertices exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G-S is at most |S|/t. We extended the Theorem of Hoàng by proving the following: Let G be a graph with degree sequence d_1,d_2, ..., d_n, and let t be a positive integer at most 4. If G is a t-tough and if for each i, t

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	QP/NLP-based Branch-and-Bound algorithm for MINLP: It could work!
Description:	Luca Mencarelli We describe a novel QP/NLP-based Branch-and-Bound algorithm for convex MINLP. Then, we introduce a tailored version of the previous algorithm for (non-convex) Binary Nonlinear Optimization Problems (BNPs), relying on a simple convexification procedure and a tailor convex quadratic under-approximation. We survey computational experiences on convex instances of MINLPLib and on several literature and random generated instances for BNPs.

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Multiplicité dans le partitionnement de graphes signés
Description:	Nejat Arinik Selon la théorie de l'équilibre structural, un graphe signé est structurellement équilibré s'il peut être partitionné en sous-groupes mutuellement hostiles (i.e. reliés seulement par des liens négatifs) tout en exhibant une solidarité interne (i.e. contenant uniquement des liens positifs). Mais un réseau réel (i.e. un graphe représentant un système du monde réel) est rarement parfaitement équilibré : on trouvera quelques liens positifs entre les groupes et/ou quelques liens négatifs à l'intérieur de certains groupes. L'un des défis du domaine est de quantifier le niveau de déséquilibre d'un tel réseau et d'identifier les liens qui causent ce déséquilibre. Le problème Correlation Clustering (CC) se définit précisément par l'obtention d'une partition possédant un déséquilibre minimal. Le partitionnement de graphes signés constitue une tâche importante du point de vue applicatif, étant donné que trouver une partition équilibrée aide à comprendre le système modélisé par le graphe signé. Cependant, l'approche standard dans la littérature se contente de chercher une seule partition, comme si elle caractérisait suffisamment le système étudié. Or, on peut avoir besoin de plusieurs partitions pour construire une image plus juste du système étudié. Même si cette notion de la multiplicité est extrêmement important du point de vue des utilisateurs finaux, elle a été très peu abordée dans la littérature. Une particulière situation dans laquelle on veut relaxer l'hypothèse de partition unique et en chercher plusieurs est lié au problème CC. Quand on résout une instance de ce problème, plusieurs partitions optimales peuvent coexister. La question qui se pose est de savoir ce qu'on perd, si on considère une seule partition optimale, alors qu'il en existe plusieurs. Idéalement, il faut les énumérer toutes avant de faire une analyse concluante. Pour ce faire, on propose une nouvelle méthode d'énumération et un framework basé sur l'analyse de clustering afin de d'abord complètement énumérer l'espace des partitions optimales, puis étudier empiriquement un tel espace. Nos résultats ont révélé une typologie de l'espace de partitions optimales : 1) une seule partition optimale ; 2) quelques partitions constituant une seule classe ; 3) beaucoup de partitions optimales constituant une seule classe de forme allongée ; 4) plusieurs partitions optimales constituant plusieurs classes de partitions.