A two-level graph partitioning problem arising in mobile wireless communications |
| |
Authors: | Jamie Fairbrother Adam N Letchford Keith Briggs |
| |
Institution: | 1.STOR-i Centre for Doctoral Training,Lancaster University,Lancaster,UK;2.Department of Management Science,Lancaster University,Lancaster,UK;3.Wireless Research Group,BT Technology, Service & Operations,Martlesham Heath, Suffolk,UK |
| |
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 subset. 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: | |
本文献已被 SpringerLink 等数据库收录! |
|