Loading...
Please wait, while we are loading the content...
Similar Documents
On Lower Bounds for the Matrix Chain Ordering Problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bradford, Phillip G. Choppella, Venkatesh Rawlins, Gregory J. E. |
| Copyright Year | 1993 |
| Abstract | This paper shows that the radix model is not reasonable for solving the Matrix Chain Ordering Problem. In particular, to have an n-matrix instance of this problem with an optimal parenthesization of depth (n) in the worst case requires the matrix dimensions to be exponential in n. Considering bit complexity, a worst case lower bound of (n) is given. This worst case lower bound is parameterized and, depending on the optimal product tree depth, it goes from (n) down to (n lgn). Also, this paper gives an (n lgn) work lower bound for the Matrix Chain Ordering Problem for a class of algorithms on the atomic comparison model with unit cost comparisons. This lower bound, to the authors' knowledge, captures all known algorithms for solving the Matrix Chain Ordering Problem, but does not consider bit operations. Finally, a trade-o is given between the bit complexity lower bound and the atomic comparison based lower bound. This trade-o basically shows that hard instances for the comparison based model are easy instances for the bit complexity model and vice versa. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.indiana.edu/ftp/techreports/TR391.pdf |
| Alternate Webpage(s) | https://www.cs.indiana.edu/l/www/ftp/techreports/TR391.pdf |
| Alternate Webpage(s) | http://www.cs.indiana.edu/pub/techreports/TR391.pdf |
| Alternate Webpage(s) | http://www.cs.indiana.edu/l/www/ftp/techreports/TR391.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Algorithm Best, worst and average case Context of computational complexity HL7PublishingSubSection |
| Content Type | Text |
| Resource Type | Article |
