Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Minimum Manhattan network problem in normed planes with polygonal balls:
  a factor 2.5 approximation algorithm   Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the
distance between two points p,q in R^2 in the normed plane whose unit ball is
B. For a set T of n points (terminals) in R^2, a B-Manhattan network on T is a
network N(T) = (V,E) with the property that its edges are parallel to the
directions of B and for every pair of terminals t_i and t_j, the network N(T)
contains a shortest B-path between them, i.e., a path of length || t_i - t_j
||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum
possible length. The problem of finding minimum B-Manhattan networks has been
introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case
when the unit ball B is a square (and hence the distance || p - q || is the l_1
or the l_infty-distance between p and q) and it has been shown recently by
Chin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation
algorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are
known. In this paper, we propose a factor 2.5 approximation algorithm for
minimum B-Manhattan network problem. The algorithm employs a simplified version
of the strip-staircase decomposition proposed in our paper (APPROX'05) and
subsequently used in other factor 2 approximation algorithms for minimum
Manhattan problem.

29
The categories of this paper are: funct-an
13
The categories of this paper are: quant-ph
0
The categories of this paper are: hep-ph
33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
4
The categories of this paper are: cond-mat
12
The categories of this paper are: nucl-th
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas
31
The categories of this paper are: ao-sci
14
The categories of this paper are: math-ph
6
The categories of this paper are: astro-ph
32
The categories of this paper are: atom-ph
3
The categories of this paper are: physics
2
The categories of this paper are: math