The balanced connected partition problem: formulations, inequalities and separation

12th of May 2022, at 13:30

Room: Online via Teams

Cliquez ici pour participer à la réunion

Speaker: Phablo Moura

Title: The balanced connected partition problem: formulations, inequalities and separation

Abstract:

 Given a connected graph G=(V,E) with nonnegative weights on the vertices, the Balanced Connected Partition Problem (BCP) consists in finding a partition {V_i}_{i=1}^k of V such that each class V_i induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCP_k is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. 
For this problem and some other natural variants, integer linear programming formulations, strong inequalities, separation algorithms and computational results with instances from an application in public security.