Sub-cubic Time Algorithm for the k-disjoint Maximum subarray Problem
| dc.contributor.author | Lee, Sang Myung (Chris) | |
| dc.date.accessioned | 2012-04-03T23:47:57Z | |
| dc.date.available | 2012-04-03T23:47:57Z | |
| dc.date.issued | 2011 | en |
| dc.description.abstract | The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. This problem was first introduced by Grenander and brought to computer science by Bentley in 1984. This problem has been branched out into other problems based on their characteristics. k-overlapping maximum subarray problem where the overlapping solutions are allowed, and k-disjoint maximum subarray problem where all the solutions are disjoint from each other are those. For k-overlapping maximum subarray problems, significant improvement have been made since the problem was first introduced. For k-disjoint maximum subarrsy, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(kn^3) time is easily obtainable for two-dimensions, little study has been undertaken to better this. This paper introduces a faster algorithm for the k-disjoint maximum sub-array problem under the conventional RAM model, based on distance matrix multiplication. Also, DMM reuse technique is introduced for the maximum subarray problem based on recursion for space optimization. | en |
| dc.identifier.uri | http://hdl.handle.net/10092/6494 | |
| dc.identifier.uri | http://dx.doi.org/10.26021/8920 | |
| dc.language.iso | en | |
| dc.publisher | University of Canterbury. Computer Science and Software Engineering | en |
| dc.relation.isreferencedby | NZCU | en |
| dc.rights | Copyright Sang Myung (Chris) Lee | en |
| dc.rights.uri | https://canterbury.libguides.com/rights/theses | en |
| dc.subject | Maximum Subarray Problem, Distance Matrix Multiplication, k-maximum Subarray Problem, k-disjoint Maximum Subarray Problem, Table-Lookup, X+Y Problem | en |
| dc.title | Sub-cubic Time Algorithm for the k-disjoint Maximum subarray Problem | en |
| dc.type | Theses / Dissertations | |
| thesis.degree.discipline | Computer Science | en |
| thesis.degree.grantor | University of Canterbury | en |
| thesis.degree.level | Masters | en |
| thesis.degree.name | Master of Science | en |
| uc.bibnumber | 1756300 | en |
| uc.college | Faculty of Science | en |
Files
Original bundle
1 - 1 of 1