Reduction from Maximum Subarray to Distance Product

From Algorithm Wiki
Revision as of 10:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: Maximum Subarray TO: Distance Product == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O(n^{3-\epsilon})$ == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/a...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

FROM: Maximum Subarray TO: Distance Product

Description

Implications

if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O(n^{3-\epsilon})$

Year

1998

Reference

Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452.

https://dl.acm.org/doi/abs/10.5555/314613.314823