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

Research

Associated organisational units

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:

Keywords

View graph of relations

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

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A two-level graph partitioning problem arising in mobile wireless communications. / Fairbrother, Jamie; Letchford, Adam Nicholas; Briggs, Keith.
In: Computational Optimization and Applications, Vol. 69, No. 3, 04.2018, p. 653-676.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Fairbrother, J, Letchford, AN & Briggs, K 2018, 'A two-level graph partitioning problem arising in mobile wireless communications', Computational Optimization and Applications, vol. 69, no. 3, pp. 653-676. https://doi.org/10.1007/s10589-017-9967-9

APA

Fairbrother, J., Letchford, A. N., & Briggs, K. (2018). A two-level graph partitioning problem arising in mobile wireless communications. Computational Optimization and Applications, 69(3), 653-676. https://doi.org/10.1007/s10589-017-9967-9

Vancouver

Fairbrother J, Letchford AN, Briggs K. A two-level graph partitioning problem arising in mobile wireless communications. Computational Optimization and Applications. 2018 Apr;69(3):653-676. Epub 2017 Nov 18. doi: 10.1007/s10589-017-9967-9

Author

Fairbrother, Jamie ; Letchford, Adam Nicholas ; Briggs, Keith. / A two-level graph partitioning problem arising in mobile wireless communications. In: Computational Optimization and Applications. 2018 ; Vol. 69, No. 3. pp. 653-676.

Bibtex

@article{1192d65ee7624d8c96e606f92148b286,
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. ",
keywords = "graph partitioning, branch-and-cut, polyhedral combinatorics, semidefinite programming",
author = "Jamie Fairbrother and Letchford, {Adam Nicholas} and Keith Briggs",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s10589-017-9967-9",
year = "2018",
month = apr,
doi = "10.1007/s10589-017-9967-9",
language = "English",
volume = "69",
pages = "653--676",
journal = "Computational Optimization and Applications",
issn = "0926-6003",
publisher = "Springer Netherlands",
number = "3",

}

RIS

TY - JOUR

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

AU - Fairbrother, Jamie

AU - Letchford, Adam Nicholas

AU - Briggs, Keith

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

PY - 2018/4

Y1 - 2018/4

N2 - 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.

AB - 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.

KW - graph partitioning

KW - branch-and-cut

KW - polyhedral combinatorics

KW - semidefinite programming

U2 - 10.1007/s10589-017-9967-9

DO - 10.1007/s10589-017-9967-9

M3 - Journal article

VL - 69

SP - 653

EP - 676

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 3

ER -