EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3656. Carousel Greedy Algorithm for the Minimum Stretch Spanning Tree Problem

Invited abstract in session MD-26: Optimization problems on graphs, stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Carmine Cerrone
University of Genoa
2. Bruce Golden
Decision & Information Technologies, University of Maryland

Abstract

The Minimum Stretch Spanning Tree Problem (MSSTP) is a variant of the classical minimum spanning tree problem. Consider a simple, connected, undirected, and unweighted graph G=(V, E), where V is the set of vertices and E is the set of edges.
The objective of MSSTP is to identify a spanning tree T=(V, E') within G that minimises the stretch, i.e., reduces the maximum distance in the spanning tree between adjacent nodes in the original graph [1]. This problem has practical applications in areas such as distribution systems, network design, transportation networks, sensor networks, phylogenetic tree reconstruction, and parallel machine architectures.
This study introduces a promising and efficient Carousel Greedy (CG) algorithm for tackling the MSSTP. The CG algorithm is a generalised greedy algorithm designed to address the conventional limitations of greedy strategies [2]. We will show that our CG algorithm outperforms the General Variable Neighbourhood Search (GVNS) in terms of solution quality, computational time, and consistency across benchmark instances.

[1] Kardam, Y. S., Srivastava, K., & Marti, R. (2023). General variable neighbourhood search for the minimum stretch spanning tree problem. Optimization Letters, 17, 2005-2031.

[2] Cerrone, C., Cerulli, R., & Golden, B. (2017). Carousel Greedy: A generalised greedy algorithm with applications in optimisation. Computers & Operations Research, 85, 97-112.

Keywords

Status: accepted


Back to the list of papers