2014

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Branch-and-Price for the relaxed clique Partitioning and Covering Problems
Description:	Roberto Wolfler Calvo Relationships between objects can be modeled with graphs, where nodes represent the different objects and edges express the relationship. Social network analysis is an example where clusters, e.g., formed by members of a community, are studied using cliques and clique relaxations. A clique is a subgraph with pairwise directly connected nodes, i.e., a subgraph with diameter one. Several relaxations have been defined either in terms of distance (k-clique), degree (k-plex, k-core), diameter (k-club), or density. The majority of the literature deals with identifying such subgraphs of maximum cardinality or weight. In this presentation, we consider the generic problem of covering or partitioning a graph with a set of relaxed cliques. We present an exact solution fromework for solving the relaxed clique partitioning and covering problems based on branch-and-price. Herein, the subproblem consists of finding a relaxed clique of maximum weight. We present heuristics and a new combinatorial branch-and-bound algorithm for its resolution. This is a join work with Fabio Furini and Stefan Irnic.