2010/04/30 by Nicolas Catusse, Catusse, Nicolas, Victor Chepoi +5
Business, Management and Accounting · Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #Facility Location and Emergency Management #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1004.5517
openalex publication_date 2010/04/30 · openalex created_date 2022/10/27 · openalex updated_date 2026/07/28
Let B be a centrally symmetric convex polygon of R2 and || p - q || be the\ndistance between two points p,q in R2 in the normed plane whose unit ball is\nB. For a set T of n points (terminals) in R2, a B-Manhattan network on T is a\nnetwork N(T) = (V,E) with the property that its edges are parallel to the\ndirections of B and for every pair of terminals ti and tj, the network N(T)\ncontains a shortest B-path between them, i.e., a path of length || ti - tj\n||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum\npossible length. The problem of finding minimum B-Manhattan networks has been\nintroduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case\nwhen the unit ball B is a square (and hence the distance || p - q || is the l1\nor the linfty-distance between p and q) and it has been shown recently by\nChin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation\nalgorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are\nknown. In this paper, we propose a factor 2.5 approximation algorithm for\nminimum B-Manhattan network problem. The algorithm employs a simplified version\nof the strip-staircase decomposition proposed in our paper (APPROX'05) and\nsubsequently used in other factor 2 approximation algorithms for minimum\nManhattan problem.\n