Mars 2018

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	On the Interplay between Simple Mixed Integer Programs and Lot-Sizing
Description:	Laurence A. Wolsey After introducing some of the most basic lot-sizing problems and their properties, we show how the study of tight MIP formulations for the convex hull of solutions of such problems has provided more general results for MIPs and vice versa. In particular we demonstrate the importance of compact extended formulations as well as the role of mixing sets, network dual MIPs and single node flow models.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Complexity of the cluster deletion problem on cographs and subclasses of chordal graphs
Description:	Mario Valencia Pabon We consider the following vertex-partition problem on graphs, known as the CLUSTER DELETION (CD) problem: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case, cliques) to minimize the total weight of edges outside the clusters. The decision version of this optimization problem is known to be NP-complete even for unweighted graphs and has been studied extensively. In this talk, I will focus on the complexity of the decision CD problem for the family of chordal graphs, showing that it is NP-complete for weighted split graphs, weighted interval graphs and unweighted chordal graphs. We will also see that the problem is NP-complete for weighted cographs. Some polynomial-time solvable cases of the optimization problem will be identified, in particular CD for unweighted cographs, split graphs, unweighted proper interval graphs and weighted block graphs. This is a joint work with Flavia Bonomo and Guillermo Duràn (University of Buenos Aires).