The Library
Fast distance multiplication of unit-Monge matrices
Tools
Tiskin, Alexander (2010) Fast distance multiplication of unit-Monge matrices. In: 21st Annual ACM/SIAM Symposium on Discrete Algorithms, Austin, TX, 17-19 Jan 2010. Published in: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, Vol.135 pp. 1287-1296. ISBN 9780898716986.
PDF
SODA10_103_tiskina.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (754Kb) |
Abstract
Monge matrices play a fundamental role in optimisation theory, graph and string algorithms Distance multiplication of two Monge matrices of size n can be performed in time O(n(2)). Motivated by applications to string algorithms, we introduced in previous works a subclass of Monge matrices, that we call simple unit-Monge matrices. We also gave a distance multiplication algorithm for such matrices, running in time O(n(15)). Landau asked whether this problem can be solved in linear time. In the current work, we give an algorithm running in time 0(n log thus approaching an answer to Landau's question within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of algorithms on strings and graphs. In particular, we obtain an algorithm for finding a maximum clique in a circle graph in time 0(n log(2) n), and a surprisingly efficient algorithm for comparing compressed strings. We also point to potential applications in group theory, by making a connection between unit-Monge matrices and Coxeter monoids We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserves further study from both the mathematical and the algorithmic viewpoints.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Proceedings in Applied Mathematics | ||||
Journal or Publication Title: | Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms | ||||
Publisher: | SIAM | ||||
ISBN: | 9780898716986 | ||||
Official Date: | 17 January 2010 | ||||
Dates: |
|
||||
Volume: | Vol.135 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 1287-1296 | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 21st Annual ACM/SIAM Symposium on Discrete Algorithms | ||||
Type of Event: | Other | ||||
Location of Event: | Austin, TX | ||||
Date(s) of Event: | 17-19 Jan 2010 | ||||
Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |