3
$\begingroup$

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$, for some $n\times n$ matrices $A$ and $B$. This lower bound means that the trivial algorithm is the best one.

Is there a better algorithm if we restrict the values to be in a finite set? For example, all the matrix entries are $0$ or $1$. Note that this is different from Boolean matrix product.

Any reference is welcome.

$\endgroup$
1
  • 1
    $\begingroup$ It is a matrix product over the semiring $(\Re_+\cup \{\infty\},\max,+)$. It can be seen as the classical matrix product where $+$ is replaced by $\max$ and $\times$ is replaced by $+$. Thus $(A^2)_{ij}=\max_{k=1}^n\{A_{ik}+A_{kj}\}$ . $\endgroup$
    – Lamine
    Feb 18, 2017 at 13:45

1 Answer 1

4
$\begingroup$

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max_{A} \sum_{a\in A} a = -\min_{A} -\sum_{a\in A}a = -\min_A \sum_{a\in A}-a$, we can express a $(\max,+)$-matrix product as a $(\min,+)$-matrix product and vice versa, as the paper allows edge-weights to be either positive or negative.

So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.