Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Polynomial Time Algorithm to Compute an Approximate Weighted Shortest
  Path   We devise a polynomial-time approximation scheme for the classical geometric
problem of finding an approximate short path amid weighted regions. In this
problem, a triangulated region P comprising of n vertices, a positive weight
associated with each triangle, and two points s and t that belong to P are
given as the input. The objective is to find a path whose cost is at most
(1+epsilon)OPT where OPT is the cost of an optimal path between s and t. Our
algorithm initiates a discretized-Dijkstra wavefront from source s and
progresses the wavefront till it strikes t. This result is about a cubic factor
(in n) improvement over the Mitchell and Papadimitriou '91 result, which is the
only known polynomial time algorithm for this problem to date. Further, with
polynomial time preprocessing of P, a set of data structures are computed which
allow answering approximate weighted shortest path queries in polynomial time.

5
The categories of this paper are: gr-qc
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
30
The categories of this paper are: q-alg
20
The categories of this paper are: acc-phys
33
The categories of this paper are: plasm-ph
16
The categories of this paper are: stat
19
The categories of this paper are: eess
25
The categories of this paper are: patt-sol
26
The categories of this paper are: bayes-an
7
The categories of this paper are: hep-th
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
4
The categories of this paper are: cond-mat