Template-type: ReDif-Paper 1.0
Author-Name: Feremans Corinne 
Author-Name: Grigoriev Alexander
Author-workplace-name: METEOR
Title: An Approximation Scheme for the Generalized Geometric Minimum Spanning Tree Problem with Grid Clustering
Abstract: This paper is concerned with a special case of the Generalized Minimum Spanning Tree Problem. The Generalized Minimum Spanning Tree Problem is de¯ned on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to ¯nd a tree of minimum cost containing exactly one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance de¯nes the edge cost. We prove that the problem admits PTAS if restricted to grid clustering.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2004
Number: 037
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:5d73ba2d-8e5c-4a13-8878-0aa427c066d4/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 185834
Handle: RePEc:unm:umamet:2004037