2 make relation between (max,+) and (min,+) more precise. edited Feb 18 '17 at 13:56 Discrete lizard♦ 5,34711 gold badge1616 silver badges4242 bronze badges 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$$, but since they allowwe 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, their techniques should be applicable to the $$(\max,+)$$ case as well.  So this gives a subcubic algorithm for $$(\max,+)$$-multiplication when the values are bounded. 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, but since they allow edge-weights to be either positive or negative, their techniques should be applicable to the $$(\max,+)$$ case as well. So this gives a subcubic algorithm when the values are bounded. 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. 1 answered Feb 18 '17 at 13:49 Discrete lizard♦ 5,34711 gold badge1616 silver badges4242 bronze badges 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, but since they allow edge-weights to be either positive or negative, their techniques should be applicable to the $$(\max,+)$$ case as well. So this gives a subcubic algorithm when the values are bounded.