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

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

Keywords:

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

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.

Downloads

Published

2006-02-01

How to Cite

Pop, P. C., Horvat-Marc, A., & Pop Sitar, C. (2006). An approximation algorithm for the at least version of the generalized minimum spanning tree problem. Rev. Anal. Numér. Théor. Approx., 35(1), 95–103. Retrieved from https://ictp.acad.ro/jnaat/journal/article/view/2006-vol35-no1-art13

Issue

Section

Articles