Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computing the Gromov hyperbolicity of a discrete metric space   We give exact and approximation algorithms for computing the Gromov
hyperbolicity of an n-point discrete metric space. We observe that computing
the Gromov hyperbolicity from a fixed base-point reduces to a (max,min) matrix
product. Hence, using the (max,min) matrix product algorithm by Duan and
Pettie, the fixed base-point hyperbolicity can be determined in O(n^2.69) time.
It follows that the Gromov hyperbolicity can be computed in O(n^3.69) time, and
a 2-approximation can be found in O(n^2.69) time. We also give a (2 log_2
n)-approximation algorithm that runs in O(n^2) time, based on a tree-metric
embedding by Gromov. We also show that hyperbolicity at a fixed base-point
cannot be computed in O(n^2.05) time, unless there exists a faster algorithm
for (max,min) matrix multiplication than currently known.

3
The categories of this paper are: physics
25
The categories of this paper are: patt-sol
35
The categories of this paper are: mtrl-th
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
16
The categories of this paper are: stat
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
10
The categories of this paper are: q-bio
14
The categories of this paper are: math-ph
18
The categories of this paper are: econ
34
The categories of this paper are: chem-ph
26
The categories of this paper are: bayes-an
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin