Novembre 2020


Retour à la vue des calendrier
Jeudi 5 Novembre
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An exact algorithm for robust influence maximization
Description: Roberto Wolfler Calvo We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robust version of the problem that we study, the node thresholds are affected by uncertainty and we optimize over a worst-case scenario within a given robustness budget. Numerical experiments show that we are able to solve to optimality instances of size comparable to other exact approaches in the literature for the non-robust problem, but in addition to this we can also tackle the robust version with similar performance.
Jeudi 19 Novembre
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
Description: Samuel Fiorini We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a 'good' cost function on the vertices at distance at most 2 from any vertex of the input graph.
As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.
Jeudi 26 Novembre
Heure: 10:30 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Émergence de nouveaux problèmes combinatoires pour les systèmes de production dans le contexte Industrie 4.0
Description: Paolo Gianessi Du fait des nouveaux paradigmes de production imposés par l'Industrie 4.0 et de l'attention grandissante portée par l'opinion publique à l'égard des questions environnementales, les systèmes de production doivent relever le double défi de répondre à une demande de plus en plus variable mais aussi faire preuve d'une efficacité énergétique accrue. De nouveaux problèmes combinatoires ont ainsi commencé à paraître dans la littérature de l'Optimisation des systèmes de production à coté des problèmes plus traditionnels. Nous en présentons ici trois, que nous avons étudiés au cours de ces deux dernières années, et qui touchent à la planification stratégique ou tactique/opérationnelle: un problème d'ordonnancement de type job-shop avec prise en compte de l'énergie; un problème d'équilibrage de ligne avec minimisation du pic de puissance; et un problème bi-niveau d'équilibrage de ligne d'un RMS (système de production reconfigurable) visant à minimiser le coût de la consommation énergétique vis-à-vis d'un plan tarifaire donné. Ces problèmes ont pour l'instant été abordés par de premières approches simples (PLNE, méta-heuristiques par décomposition et/où recherche locale) afin d'en démontrer l'intérêt pratique auprès de la communauté industrielle; il paraît tout de même évident qu'ils offrent des développements potentiels à investiguer aussi d'un point de vue plus proprement algorithmique et combinatoire, et par conséquent s'affichent comme de nouveaux éléments d'intérêt certain de la frontière entre applications réelles et recherche fondamentale.