A Three-Phase Search Approach for the Quadratic Minimum Spanning Tree Problem
Given an undirected graph with costs associated with each edge as well as each pair of edges, the quadratic minimum spanning tree problem (QMSTP) consists of determining a spanning tree of minimum total cost. This problem can be used to model many real-life network design applications, in which both routing and interference costs should be considered. For this problem, we propose a three-phase search approach named TPS, which integrates 1) a descent-based neighborhood search phase using two different move operators to reach a local optimum from a given starting solution, 2) a local optima exploring phase to discover nearby local optima within a given regional search area, and 3) a perturbation-based diversification phase to jump out of the current regional search area. Additionally, we introduce dedicated techniques to reduce the neighborhood to explore and streamline the neighborhood evaluations. Computational experiments based on hundreds of representative benchmarks show that TPS produces highly competitive results with respect to the best performing approaches in the literature by improving the best known results for 31 instances and matching the best known results for the remaining instances only except two cases. Critical elements of the proposed algorithms are analyzed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We …
FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
We present Fast Approximate Minimum Spanning Tree (FAMST), a novel algorithm that addresses the computational challenges of constructing Minimum Spanning Trees (MSTs) for large-scale and high-dimensional datasets. FAMST …
Minimum Phase Linear Antenna Array Design
The paper considers the design of minimum phase discrete linear arrays. The paper introduces recent advances for the design of minimum phase Finite Impulse Response filters, as applied to the design of minimum phase line…
A Minimum Spanning Tree Representation of Anime Similarities
In this work, a new way to represent Japanese animation (anime) is presented. We applied a minimum spanning tree to show the relation between anime. The distance between anime is calculated through three similarity measu…
New characterizations of minimum spanning trees and of saliency maps based on quasi-flat zones
We study three representations of hierarchies of partitions: dendrograms (direct representations), saliency maps, and minimum spanning trees. We provide a new bijection between saliency maps and hierarchies based on quas…