Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Divide and conquer!

Problem description

Imagine you are an administrator of a large estate with many towns, villages and a network of roads connecting them. You have already got tired of all the daily duties and you decide to divide the whole land into smaller districts and to delegate the administration duties to your deputies, each deputy controlling one district.

The goal is to divide the original area into maximally autonomous regions, i.e., minimally interconnected regions.

Input: Graph <latex>$G(V,E)$</latex>, where V is a set of towns <latex>${v_1,…,v_M}$</latex> and E is a set of roads connecting the towns. n is the number of regions to which the whole area is to be divided.

Output: Partitioning of the set V into equally-sized and disjoint subsets <latex>${V_1,…,V_n}$</latex>, where <latex>$\bigcup_{i=1}^{n}V_i=V$</latex> and <latex>$||V_i|-|V_j||\leq 1$</latex> for all <latex>$i\neq j$</latex> such that the inter-connectivity of the regions is minimized subject to the constraint imposed on the regions size.

Possible representations

  • Array of size M, where the value at i-th position represents the identifier of the region, to which the i-th town is assigned.

Uniform evaluation function

The number of roads interconnecting towns from different regions. This means, the number of all roads between towns $t_i$ and $t_j$, where $t_i$ belongs to different region than $t_j$.

<latex> \begin{equation*} f(s) = \sum_{l\in V_i, k\in V_j,i\neq j}e_{lk} \end{equation*} </latex>

where $e_{lk}$ is an item from the edge matrix (it is 1 if $l$ is connected to $k$; 0 otherwise). This function is to be minimized.

Multi-objective extension

It is possible to solve this problem as the multi-objective one

  • 1st objective is to minimize the inter-connectivity of the regions
  • 2nd objective is to minimize the size differences among the regions.

This way it might be possible to find regions of great autonomy while being of very similar size.

courses/a0m33eoa/semestral_tasks/divide_and_conquer.txt · Last modified: 2022/11/14 10:27 by xposik