EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Metaheuristics
- Algorithms
- Graphs and Networks
Status: accepted
Back to the list of papers