Ricerc@Sapienza

We study various polynomial special cases for the problem of partitioning a vertex-weighted undirected graph into p connected subgraphs with minimum gap between the largest and the smallest vertex weight

This paper addresses centered and non centered equipartition tree problems into connected components (p-partitions). In the former case, each partition must contain exactly one special vertex called center, whereas in the latter, partitions are not required to fulfill this condition. Among the different equipartition problems considered in the literature, we focus on: (1) Most Uniform Partition (MUP) and (2) Uniform Partition (UP). Both criteria are defined either w.r.t. weights assigned to each vertex or to costs assigned to each vertex–center pair.

Political districting is a very well-known technical problem related to electoral systems in which the transformation of votes into seats depends on the subdivision of the national electoral body into a given number of smaller territorial bodies. After a proper discretization of the territory, the problem consists of partitioning the territory into a prefixed number of regions which satisfy a set of geographic and demographic criteria.

Research assessment exercises have enjoyed ever-increasing popularity in many countries in recent years, both as a method to guide public funds allocation and as a validation tool for adopted research support policies. Italy’s most recently completed evaluation effort (VQR 2011–14) required each university to submit to the Ministry for Education, University, and Research (MIUR) 2 research products per author (3 in the case of other research institutions), chosen in such a way that the same product is not assigned to two authors belonging to the same institution.