Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: $\{-1,0,1\}$-APSP and (min,max)-Product Problems   In the $\{-1,0,1\}$-APSP problem the goal is to compute all-pairs shortest
paths (APSP) on a directed graph whose edge weights are all from $\{-1,0,1\}$.
In the (min,max)-product problem the input is two $n\times n$ matrices $A$ and
$B$, and the goal is to output the (min,max)-product of $A$ and $B$.
  This paper provides a new algorithm for the $\{-1,0,1\}$-APSP problem via a
simple reduction to the target-(min,max)-product problem where the input is
three $n\times n$ matrices $A,B$, and $T$, and the goal is to output a Boolean
$n\times n$ matrix $C$ such that the $(i,j)$ entry of $C$ is 1 if and only if
the $(i,j)$ entry of the (min,max)-product of $A$ and $B$ is exactly the
$(i,j)$ entry of the target matrix $T$. If (min,max)-product can be solved in
$T_{MM}(n) = \Omega(n^2)$ time then it is straightforward to solve
target-(min,max)-product in $O(T_{MM}(n))$ time. Thus, given the recent result
of Bringmann, K\"unnemann, and Wegrzycki [STOC 2019], the $\{-1,0,1\}$-APSP
problem can be solved in the same time needed for solving approximate APSP on
graphs with positive weights.
  Moreover, we design a simple algorithm for target-(min,max)-product when the
inputs are restricted to the family of inputs generated by our reduction. Using
fast rectangular matrix multiplication, the new algorithm is faster than the
current best known algorithm for (min,max)-product.

24
The categories of this paper are: dg-ga
17
The categories of this paper are: q-fin
30
The categories of this paper are: q-alg
16
The categories of this paper are: stat
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
29
The categories of this paper are: funct-an
19
The categories of this paper are: eess
23
The categories of this paper are: solv-int
18
The categories of this paper are: econ
35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
2
The categories of this paper are: math
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics