An approximation algorithm for the at least version of the generalized minimum spanning tree problem
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 ass...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Publishing House of the Romanian Academy
2006-02-01
|
| Series: | Journal of Numerical Analysis and Approximation Theory |
| Subjects: | |
| Online Access: | https://ictp.acad.ro/jnaat/journal/article/view/1016 |
| _version_ | 1818006038739156992 |
|---|---|
| author | Petrică C. Pop Andrei Horvat-Marc Corina Pop Sitar |
| author_facet | Petrică C. Pop Andrei Horvat-Marc Corina Pop Sitar |
| author_sort | Petrică C. Pop |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-14T04:55:06Z |
| format | Article |
| id | doaj.art-87b58ccc7c6e46c7943dac638a9d70ec |
| institution | Directory Open Access Journal |
| issn | 2457-6794 2501-059X |
| language | English |
| last_indexed | 2024-04-14T04:55:06Z |
| publishDate | 2006-02-01 |
| publisher | Publishing House of the Romanian Academy |
| record_format | Article |
| series | Journal of Numerical Analysis and Approximation Theory |
| spelling | doaj.art-87b58ccc7c6e46c7943dac638a9d70ec2022-12-22T02:11:11ZengPublishing House of the Romanian AcademyJournal of Numerical Analysis and Approximation Theory2457-67942501-059X2006-02-01351An approximation algorithm for the at least version of the generalized minimum spanning tree problemPetrică C. Pop0Andrei Horvat-Marc1Corina Pop Sitar2North University of Baia Mare, RomaniaNorth University of Baia Mare, Romania“Babes-Bolyai” University, Cluj-Napoca, RomaniaWe 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.https://ictp.acad.ro/jnaat/journal/article/view/1016approximation algorithmsminimum spanning treegeneralized minimum spanning treesinteger programminglinear relaxation |
| spellingShingle | Petrică C. Pop Andrei Horvat-Marc Corina Pop Sitar An approximation algorithm for the at least version of the generalized minimum spanning tree problem Journal of Numerical Analysis and Approximation Theory approximation algorithms minimum spanning tree generalized minimum spanning trees integer programming linear relaxation |
| title | An approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| title_full | An approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| title_fullStr | An approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| title_full_unstemmed | An approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| title_short | An approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| title_sort | approximation algorithm for the at least version of the generalized minimum spanning tree problem |
| topic | approximation algorithms minimum spanning tree generalized minimum spanning trees integer programming linear relaxation |
| url | https://ictp.acad.ro/jnaat/journal/article/view/1016 |
| work_keys_str_mv | AT petricacpop anapproximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem AT andreihorvatmarc anapproximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem AT corinapopsitar anapproximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem AT petricacpop approximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem AT andreihorvatmarc approximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem AT corinapopsitar approximationalgorithmfortheatleastversionofthegeneralizedminimumspanningtreeproblem |