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

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

# $(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.