Multiplication Algorithms for Monge Matrices
Luís M. S. Russo,
INESC-ID Lisboa and IST –
In this talk we will 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 have several applications in bioinformatics, in particular Monge matrices occur in genome alignment problems.
Date: 2010-Sep-17 Time: 14:00:00 Room: 336
For more information:
INESC Brussels HUB Winter Meeting | JAN 25-26, 2024, in Porto
The INESC Winter Meeting, organized in collaboration with INESC Holding, is scheduled for January 25th and 26th, 2024, and it will be held in the city of Porto.
On January 25th, the primary goal is to bring together individuals from all five INESC institutes, fostering an environment that encourages networking, forging new connections, and collectively engaging in a forward-thinking exercise regarding the future of our research fields and the positioning of the INESC group within the European landscape.
There will be a welcome lunch, followed by an afternoon dedicated to collaboration, openness, and curiosity. The event will have a participatory approach, and will be guided by Dirk Stockmans, a highly experienced facilitator who has worked for the European Commission for the last 30 years.
Furthermore, all INESC researchers are invited to submit proposals for e-posters to be displayed at the Winter Meeting. Deadline for submissions is December 10 and more information is available here.
On January 26th, a senior administration and management committee will be held. Participants will be selected by each institute administration by invitation only.
If you would to take part on the 25th of January, please register here by November 30th.
The INESC Brussels HUB website will soon share more information about the venue and uptaded agenda.