Template-type: ReDif-Paper 1.0
Author-Name: Feremans,Corinne
Author-Name: Grigoriev,Alexander 
Author-workplace-name: METEOR
Title: Approximation schemes for the generalized geometric problems with geographic clustering
Abstract: This paper is concerned with polynomial time approximations schemes for the generalized geometric problems with geographic clustering. We illustrate the approach on the generalized traveling salesman problem which is also known as Group-TSP or TSP with neighborhoods. We prove that under the condition that all regions are non-intersecting and have comparable sizes and shapes, the problem admits PTAS. To derive a PTAS we extend the algorithm by Arora [2]. This extension involves the dissection mechanism and solution of the selection problem. We observe that the results are applicable to many generalized geometric problems, to other Minkowski norms, and to other ¯xed dimensional spaces.
Keywords: Economics ; 
Series: Research Memoranda
Creation-Date: 2004
Number: 034
File-URL: http://edocs.ub.unimaas.nl/loader/file.asp?id=919
File-Format: application/pdf
File-Size: 119855
Handle: RePEc:unm:umamet:2004034