Article

Free access

Algorithms for the maximum subarray problem based on matrix multiplication

Authors:

Hisao Tamaki,

Takeshi TokuyamaAuthors Info & Claims

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

Pages 446 - 452

Published: 01 January 1998 Publication History

PDF eReader

References

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms Addison- Wesley, 1974.

Digital Library

Google Scholar

[2]

R. Agrawal, T. Imielinski and A. Swami, Mining Association Rules between Sets of Items in Large Databases, Proc. A CM SIGMOD Con/'. on Management of Data, (1993) 207-216.

Digital Library

Google Scholar

[3]

N. Alon, Z. Galil, and O. Margalit, On the Exponent of the All Pairs Shortest Path Problem, Proc. 3~nd FOCS (1991), 569-575.

Digital Library

Google Scholar

[4]

J. Bentley, Programming Pearls- Algorithm Design Techniques, CA CM 27-9, (1984) pp.865-871.

Digital Library

Google Scholar

[5]

J. Bentley, Programming Pearls- Perspective on Performance, CA CM 27-11, (1984) pp.1087-1092.

Digital Library

Google Scholar

[6]

D. Coppersmith and S. Winograd, Matrix Multiplication via Arithmetic Progression, J. Symboric Computation 9 (1990) pp.251-280.

Digital Library

Google Scholar

[7]

D. Dobkin and D. Eppstein, Computing the Discrepancy, Proc. 9th A CM Syrup. Computational Geometry (1993), pp.47-52.

Digital Library

Google Scholar

[8]

D. Dobkin and D. Gunopulos, Computing the Rectangle Discrepancy, Proc. 10th A CM Syrup. Computa. tional Geometry (1994) pp. 385-386.

Digital Library

Google Scholar

[9]

P. Fisher, K. U. H6ffgen, H. Lefmann, and T. Luczak, Approximations with Axis Parallel Rectangles, Proc. FCT'93 Springer LNCS 710, (1993), pp.244-255.

Digital Library

Google Scholar

[10]

M. L. Fredman, New Bounds on the Complexity of the Shortest Path Problem SIAM J. Comput. 5 (1976) pp. 83-89.

Google Scholar

[11]

T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, Data Mining Using Two-Dimensional Optimized Association Rules: Scheme, Algorithms, and Visualization, Proc. A CM SIGMOD Conf. on Management of Data (1996) pp. 13-~3.

Digital Library

Google Scholar

[12]

T. Fukuda, Y. Morimoto, S. Morishita and T. Tokuyaxaa, Constructing EiHcient Decision Trees by Using Optimized Association Rules, Proc. ~end VLDB Conference, (1996) pp. 146-155.

Digital Library

Google Scholar

[13]

D. Kerger, D. Koller, and S. J. Phillips, Finding the Hidden Path; Time bounds for All-Pairs Shortest Path, SIAM J. Comput., 22 (1993), pp.1199-1217

Digital Library

Google Scholar

[14]

L.R. Kerr, The effect of algebraic structure on the computational complezity of matri~ multiplications~ Ph. D. Thesis, Cornel University, 1970.

Digital Library

Google Scholar

[15]

K. Mehlhorn and B. Pribe, On the All-Pairs Shortest- Path Algorithm of Moffat and Takaoka, Random Structures and Algorithms 10 (1997), pp. 205-220.

Digital Library

Google Scholar

[16]

Y. Morimoto, T. Fukuda, S. Morishita, and T. Tokuyama, Implementation and Evaluation of Decision Trees with Range and Region Splitting, to appear in Constraints.

Digital Library

Google Scholar

[17]

H. Neiderreiter, Random Number Generation and Quasi-Monte Carlo Methods, CGMS-NSF Conference Series in Appl. Math. 63, SIAM, 1992

Digital Library

Google Scholar

[18]

K. Perumalla and N. Deo, Parallel algorithms for maximum subsequence and maximum subarray, Parallel Processing Letters 5-3, (1995), pp.367-73.

Google Scholar

[19]

T. Takaoka, A new upper bound on the complexity of the all pairs shortest path problem, 1PL 43 (1992), pp. 195-199

Digital Library

Google Scholar

[20]

S. Tezuka, Uniform Random Numbers; Theory and Practice, Kluwer Academic Publishers, 1995.

Google Scholar

[21]

S. Tezuka and T. Tokuyama, A Note on Polynomial Arithmetic Analogue of Halton Sequences, Acre Trans. Modeling and Comput. Simulation 4, (1994) pp. 279- 284.

Digital Library

Google Scholar

[22]

K. ~oda, T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, Computing Optimized Rectilinear Regions for Association Rules and Highly Accurate Decision Trees, Proc. 3rd International Conference on Knowledge Discovery and Data Mining. pp. 96-103, 1997.

Google Scholar

Cited By

View all

Lincoln AWilliams VWilliams RCzumaj A(2018)Tight hardness for shortest cycles and paths in sparse graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175350(1236-1252)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175350
Williams VWilliams R(2018)Subcubic Equivalences Between Path, Matrix, and Triangle ProblemsJournal of the ACM10.1145/318689365:5(1-38)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3186893
Bae SShinn TTakaoka T(2016)An efficient parallel algorithm for the maximum convex sum problemProceedings of the Australasian Computer Science Week Multiconference10.1145/2843043.2843049(1-7)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1145/2843043.2843049
Show More Cited By

Index Terms

Algorithms for the maximum subarray problem based on matrix multiplication
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Randomness, geometry and discrete structures

Recommendations

Improved Algorithms for the K-Maximum Subarray Problem

The maximum subarray problem is to find the contiguous array elements having the largest possible sum. We extend this problem to find K maximum subarrays. For general K maximum subarrays where overlapping is allowed, Bengtsson and Chen presented $$O\...
Algorithms for Iterative Array Multiplication

Algorithms for the parallel multiplication of two n- bit binary numbers by an iterative array of logic cells are discussed. The regular interconnection structures of the multiplier array cell elements, which are ideal for VLSI implementation, are ...
Generalized matrix inversion is not harder than matrix multiplication

Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

January 1998

704 pages

ISBN:0898714109

Chairman:
Howard Karloff

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Check for updates

Qualifiers

Article

Conference

SODA98

Sponsor:

SIGACT
SIAM

SODA98: 1998 Conference on Discrete Algorithms

January 25 - 27, 1998

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
1,218
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)11

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lincoln AWilliams VWilliams RCzumaj A(2018)Tight hardness for shortest cycles and paths in sparse graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175350(1236-1252)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175350
Williams VWilliams R(2018)Subcubic Equivalences Between Path, Matrix, and Triangle ProblemsJournal of the ACM10.1145/318689365:5(1-38)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3186893
Bae SShinn TTakaoka T(2016)An efficient parallel algorithm for the maximum convex sum problemProceedings of the Australasian Computer Science Week Multiconference10.1145/2843043.2843049(1-7)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1145/2843043.2843049
Shafiul Alam MMukhopadhyay A(2016)Algorithms for Problems on Maximum Density SegmentProceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 960210.1007/978-3-319-29221-2_2(14-25)Online publication date: 18-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-319-29221-2_2
Takaoka T(2014)Efficient parallel algorithms for the maximum subarray problemProceedings of the Twelfth Australasian Symposium on Parallel and Distributed Computing - Volume 15210.5555/2667672.2667678(45-50)Online publication date: 20-Jan-2014
https://dl.acm.org/doi/10.5555/2667672.2667678
Morihata A(2012)Calculational developments of new parallel algorithms for size-constrained maximum-sum segment problemsProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_18(213-227)Online publication date: 23-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29822-6_18
Lempitsky VZisserman A(2010)Learning To count objects in imagesProceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 110.5555/2997189.2997337(1324-1332)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997189.2997337
Anzai SChun JKasai RKorman MTokuyama T(2010)Effect of corner information in simultaneous placement of K rectangles and tableauxProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886844(235-243)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886844
Lin TLee D(2010)Efficient algorithms for the sum selection problem and k maximum sums problemTheoretical Computer Science10.1016/j.tcs.2009.11.005411:7-9(986-994)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.11.005
Bae STakaoka T(2007)A sub-cubic time algorithm for the k-maximum subarray problemProceedings of the 18th international conference on Algorithms and computation10.5555/1781574.1781657(751-762)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.5555/1781574.1781657
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improved Algorithms for the K-Maximum Subarray Problem

Algorithms for Iterative Array Multiplication

Generalized matrix inversion is not harder than matrix multiplication