@article{Pop_Horvat-Marc_Pop Sitar_2006, title={An approximation algorithm for the at least version of the generalized minimum spanning tree problem}, volume={35}, url={https://ictp.acad.ro/jnaat/journal/article/view/2006-vol35-no1-art13}, DOI={10.33993/jnaat351-1016}, abstractNote={<pre>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. <br>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.<br>The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. <br>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.</pre>}, number={1}, journal={Rev. Anal. Numér. Théor. Approx.}, author={Pop, Petrică C. and Horvat-Marc, Andrei and Pop Sitar, Corina}, year={2006}, month={Feb.}, pages={95–103} }