6533b85ffe1ef96bd12c23a5

RESEARCH PRODUCT

Guided local search for the optimal communication spanning tree problem

Wolfgang SteitzFranz Rothlauf

subject

Distributed minimum spanning treeTree (data structure)Tree traversalMathematical optimizationSpanning treeOptimal binary search treeGuided Local SearchMinimum spanning treeMetaheuristicMathematics

description

This paper considers the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions. Consequently, integrating this knowledge into a metaheuristic increases its performance for the OCST problem. In this paper, we present a guided local search (GLS) approach which dynamically changes the objective function to guide the search process into promising areas. In contrast to traditional approaches which reward promising solution features by favoring edges with low weights pointing towards the tree's center, GLS penalizes low-quality edges with large weights that do not point towards the tree's center.

https://doi.org/10.1145/2001858.2001889