$(max,+)$ matrix product with limited number of values
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.