2 Add definition of $(max,+)$ matrix product.
source | link

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). And thusThis 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.

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). And thus 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.

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.

1
source | link

$(max,+)$ matrix product with limited number of values

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). And thus 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.