%0 Journal Article
%T Approximation Algorithms for Generalized MST and TSP in Grid Clusters
%A Binay Bhattacharya
%A Ante £¿usti£¿
%A Akbar Rafiey
%A Arash Rafiey
%A Vladyslav Sokol
%J Computer Science
%D 2015
%I arXiv
%X We consider a special case of the generalized minimum spanning tree problem (GMST) and the generalized travelling salesman problem (GTSP) where we are given a set of points inside the integer grid (in Euclidean plane) where each grid cell is $1 \times 1$. In the MST version of the problem, the goal is to find a minimum tree that contains exactly one point from each non-empty grid cell (cluster). Similarly, in the TSP version of the problem, the goal is to find a minimum weight cycle containing one point from each non-empty grid cell. We give a $(1+4\sqrt{2}+\epsilon)$ and $(1.5+8\sqrt{2}+\epsilon)$-approximation algorithm for these two problems in the described setting, respectively. Our motivation is based on the problem posed in [7] for a constant approximation algorithm. The authors designed a PTAS for the more special case of the GMST where non-empty cells are connected end dense enough. However, their algorithm heavily relies on this connectivity restriction and is unpractical. Our results develop the topic further.
%U http://arxiv.org/abs/1507.04438v1