Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Some recent results on the integer linear programming formulation for the Max-Cut problem
Hung Nguyen

30 November 2018, 00h00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche : Théorie des graphes

Résumé :
Given an undirected graph G=(V,E) where the edges are weighted by an arbitrary cost vector, a cut in G associated with a node subset S is the edge subset of E which contains all the edges having exactly one end-node in S.
The Maximum Cut problem which is to find a maximum total weight cut in G is one of the fundamental problems in combinatorial optimization.
The problem is NP-hard and has applications in many areas such as statistical physics, VLSI circuit design, scheduling, ...
Exact solutions for Max-Cut are usually based on mathematical formulations such as SDP for dense graphs and integer linear programming for sparse graphs.
The latter has non-compact formulations using cycle inequalities in the original space and compact (i.e., polynomial size) extended formulations using O(n^3) triangle inequalities defined on the complete graph of n vertices. In this talk, we show that one can simply reduce the number of triangle inequalities to O(nm).
We also present several extensions of the result for special sparse graphs and for graph partitioning problem.

Pour en savoir plus :
Séminaires
Heterogeneous Treatment Effects Estimation: When M
Raisonnement automatique
Thursday 02 June 2022 - 10h30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Langages et systèmes centrés données
Monday 30 May 2022 - 00h00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00h00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Raisonnement automatique
Thursday 07 April 2022 - 10h30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11h00
Salle : 455 - PCRI-N
Thomas Haschka .............................................