Title: A Two-Level Graph Partitioning Problem Arising in Mobile Wireless Communications,
Abstract: In the k-partition problem (k-PP), one is given an edge-weighted undirected
graph, and one must partition the node set into at most k subsets, in order to
minimise (or maximise) the total weight of the edges that have their end-nodes
in the same cluster. Various hierarchical variants of this problem have been
studied in the context of data mining. We consider a 'two-level' variant that
arises in mobile wireless communications. We show that an exact algorithm based
on intelligent preprocessing, cutting planes and symmetry-breaking is capable
of solving small- and medium-size instances to proven optimality, and providing
strong lower bounds for larger instances.