$(max,+)$ matrix product with limited number of values - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T16:39:23Z https://cs.stackexchange.com/feeds/question/70463 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/70463 3 $(max,+)$ matrix product with limited number of values Lamine https://cs.stackexchange.com/users/42047 2017-02-18T13:19:18Z 2018-12-10T19:52:30Z <p>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.</p> <p>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. </p> <p>Any reference is welcome. </p> https://cs.stackexchange.com/questions/70463/-/70466#70466 4 Answer by Discrete lizard for $(max,+)$ matrix product with limited number of values Discrete lizard https://cs.stackexchange.com/users/65339 2017-02-18T13:49:33Z 2017-02-18T13:56:57Z <p>The paper <a href="https://arxiv.org/abs/cs/0008011" rel="nofollow noreferrer">All pairs shortest paths using bridging sets and rectangular matrix multiplication</a> 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. </p> <p>So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.</p>