Exact and approximate solutions for balanced connected partition problems with applications in public security

Abstract

In this seminar, we address the balanced connected $k$-partition problem ($BCP_k$) from an algorithmic perspective. Given a connected graph $G=(V,E)$ with nonnegative weights on the vertices, the problem 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, we show approximation algorithms, integer linear programming formulations, strong inequalities and computational results with instances from an application in public security.