An approximation algorithm for the at least version of the generalized minimum spanning tree problem

Petrică C. Pop; Andrei Horvat-Marc; Corina Pop Sitar

doi:10.33993/jnaat351-1016

Authors

Petrică C. Pop North University of Baia Mare, Romania
Andrei Horvat-Marc North University of Baia Mare, Romania
Corina Pop Sitar “Babes-Bolyai” University, Cluj-Napoca, Romania

DOI:

https://doi.org/10.33993/jnaat351-1016

Keywords:

approximation algorithms, minimum spanning tree, generalized minimum spanning trees, integer programming, linear relaxation

Abstract views: 307

Abstract

We consider the at least version of the Generalized Minimum Spanning Tree Problem, denoted by L-GMSTP, which consists in finding a minimum cost tree spanning at least one node from each node set of a complete graph with the nodes partitioned into a given number of node sets called clusters.
We assume that the cost function attached to edges satisfies the triangle inequality and the clusters have sizes bounded by \(\rho\). Under these assumptions we present a 2\(\rho\) approximation algorithm.
The algorithm works by rounding an optimal fractional solution to a linear programming relaxation.
Our technique is based on properties of optimal solutions to the linear programming formulation of the minimum spanning tree problem and the parsimonious property of Goemans and Bertsimas.

Downloads

Download data is not yet available.

References

Dror, M., Haouari, M. and Chaouachi, J., Generalized Spanning Trees, European Journal of Operational Research, 120, pp. 583-592, 2000, https://doi.org/10.1016/s0377-2217(99)00006-5 DOI: https://doi.org/10.1016/S0377-2217(99)00006-5

Feremans, C., Generalized Spanning Trees and Extensions, PhD thesis, Universite Libre de Bruxelles, Belgium, 2001. DOI: https://doi.org/10.1016/S0377-2217(00)00267-8

Feremans, C., Labbe, M. and Laporte, G., A Comparative analysis of several formulations of the generalized minimum spanning tree problem, Networks, 39, no. 1, pp. 29-34, 2002, https://doi.org/10.1002/net.10009 DOI: https://doi.org/10.1002/net.10009

Goemans, M.X. and Bertsimas, D.J., Survivable networks, linear programming relaxations and parsimonious property, Mathematical programming, 60, pp. 145-166, 1993, https://doi.org/10.1007/bf01580607 DOI: https://doi.org/10.1007/BF01580607

Grötschel, M., Lovász, L. and Schrijver, A., Geometric Algorithm and Combinatorial Optimization, Springer-Verlag, Berlin, 1988,https://doi.org/10.1007/978-3-642-97881-4 DOI: https://doi.org/10.1007/978-3-642-97881-4

Myung, Y.S., Lee, C.H. and Tcha, D.W., On the generalized minimum spanning tree problem, Networks, 26, pp. 231-241, 1995, https://doi.org/10.1002/net.3230260407 DOI: https://doi.org/10.1002/net.3230260407

Pop, P.C., The Generalized Minimum Spanning Tree Problem, PhD thesis, University of Twente, The Netherlands, 2002. DOI: https://doi.org/10.1016/S0377-2217(02)00213-8

Pop, P.C., New models of the generalized minimum spanning tree problem, Journal of Mathematical Modelling and Algorithms, 3, no. 2, pp. 153-166, 2004, https://doi.org/10.1023/b:jmma.0000036579.83218.8d DOI: https://doi.org/10.1023/B:JMMA.0000036579.83218.8d

Pop, P.C., On the Prize-Collecting Generalized Minimum Spanning Tree Problem, to appear in Annals of Operations Research, https://doi.org/10.1007/s10479-006-0153-1 DOI: https://doi.org/10.1007/s10479-006-0153-1

Pop, P.C., Kern, W. and Still, G., Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem, Rev. Anal. Numér. Theor. Approx., 34, no. 1, pp. 93-102, 2005, http://ictp.acad.ro/jnaat/journal/article/view/2005-vol34-no1-art10

Pop, P.C., Kern, W. and Still, G., A new relaxation method for the generalized minimum spanning tree problem, European Journal of Operational Research, 170, pp. 900-908, 2006, https://doi.org/10.1016/j.ejor.2004.07.058 DOI: https://doi.org/10.1016/j.ejor.2004.07.058

Roos, C., Terlaky, T. and Vial, J.-Ph., Theory and Algorithms for Linear Optimization. An Interior Point Approach, John Wiley & Sons, 1997.