Multiplication Algorithms for Monge Matrices
Abstract:
In this paper we study algorithms for the max-plus product of Monge
matrices. These algorithms use the underlying regularities of the
matrices to be faster than the general multiplication algorithm,
hence saving time. A non-naive solution is to iterate the SMAWK
algorithm. For specific classes there are more efficient
algorithms. We present a new multiplication algorithm (MMT), that is
efficient for general Monge matrices and also for specific classes. The
theoretical and empirical analysis shows that MMT operates in near
optimal space and time. Hence we give further insight into an open
problem proposed by Landau. The resulting algorithms are relevant
for bio-informatics, namely because Monge matrices occur in string
alignment problems.
Luis Russo
2010-08-10