Randomized Algorithm for the Sum Selection Problem
Resource
Theoretical Computer Science, vol.377(1), pp.151-156, 2007
Journal
Algorithms and Computation (Lecture Notes in Computer Science)
Pages
515-523
Date Issued
2007
Date
2007
Author(s)
Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Rangan, C. Pandu
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Dough
Vardi, Moshe Y.
Weikum, Gerhard
Abstract
Given a sequence of n real numbers A = a1, a 2,⋯, an and a positive integer k, the SUM SELECTION PROBLEM is to find the segment A(i, j) = ai, a i+1,⋯, aj such that the rank of the sum s(i, j) = Σt=ijat is k over all n(n-1)/2 segments. We will give a randomized algorithm for this problem that runs in expected O(n log n) time. Applying this algorithm we can obtain an algorithm for the k MAXIMUM SUMS PROBLEM, i.e., the problem of enumerating the k largest sum segments, that runs in expected O(n log n + k) time. The previously best known algorithm for the k MAXIMUM SUMS PROBLEM runs in O(n log2n + k) time in the worst case. © Springer-Verlag Berlin Heidelberg 2005.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
903.pdf
Size
23.97 KB
Format
Adobe PDF
Checksum
(MD5):fbd7faafd5a1f69253d08536e1bc70c7