Efficient lower and upper bounds for the weight-constrained minimum spanning tree problem using simple Lagrangian based algorithms

Cristina Requejo () and Eulália Santos ()
Additional contact information
Cristina Requejo: University of Aveiro
Eulália Santos: ISLA-Higher Institute of Leiria and Santarém

Operational Research, 2020, vol. 20, issue 4, No 22, 2467-2495

Abstract: Abstract The weight-constrained minimum spanning tree problem (WMST) is a combinatorial optimization problem for which simple but effective Lagrangian based algorithms have been used to compute lower and upper bounds. In this work we present several Lagrangian based algorithms for the WMST and propose two new algorithms, one incorporates cover inequalities. A uniform framework for deriving approximate solutions to the WMST is presented. We undertake an extensive computational experience comparing these Lagrangian based algorithms and show that these algorithms are fast and present small integrality gap values. The two proposed algorithms obtain good upper bounds and one of the proposed algorithms obtains the best lower bounds to the WMST.

Keywords: Weighted minimum spanning tree; Minimum spanning tree; Lagrangian based algorithms (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-018-0426-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:20:y:2020:i:4:d:10.1007_s12351-018-0426-x

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-018-0426-x

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().