Home > Research > Publications & Outputs > A two-level graph partitioning problem arising ...

Electronic data

  • arxiv_paper

    Submitted manuscript, 335 KB, PDF document

  • kpp-projection

    Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s10589-017-9967-9

    Accepted author manuscript, 335 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

A two-level graph partitioning problem arising in mobile wireless communications

Research output: Contribution to journalJournal article

Published
<mark>Journal publication date</mark>04/2018
<mark>Journal</mark>Computational Optimization and Applications
Issue number3
Volume69
Number of pages24
Pages (from-to)653-676
Publication statusPublished
Early online date18/11/17
Original languageEnglish

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.

Bibliographic note

The final publication is available at Springer via http://dx.doi.org/10.1007/s10589-017-9967-9