# A Two-Level Graph Partitioning Problem Arising in Mobile Wireless Communications

arXiv: https://arxiv.org/abs/1705.08773 · HTML: https://mlsanity.com/paper/1705.08773/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2017.

## Built on by (most cited first, 1 of 1)

- [Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment](https://mlsanity.com/paper/2608.21485/) (2026)

## Abstract (arXiv)

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.