Please wait ... |

Link to record
http://ltu.diva-portal.org/smash/person.jsf?pid=authority-person:56794 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt142_recordDirectLink",{id:"formSmash:upper:j_idt142:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt142_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt142_j_idt144",{id:"formSmash:upper:j_idt142:j_idt144",widgetVar:"widget_formSmash_upper_j_idt142_j_idt144",target:"formSmash:upper:j_idt142:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Chen, Jingsen

Open this publication in new window or tab >>In-place heap construction with optimized comparisons, moves, and cache misses### Chen, Jingsen

### Edelkamp, Stefan

### Elmasry, Amr

### Katajainen, Jyrki

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_some",{id:"formSmash:j_idt204:0:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_otherAuthors",{id:"formSmash:j_idt204:0:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_otherAuthors",multiple:true}); 2012 (English)In: Mathematical foundations of computer science 2012: 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012 : proceedings / [ed] Branislav Rovan; Vladimiro Sassone ; Peter Widmayer, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2012, p. 259-270Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2012
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 7464
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-27310 (URN)10.1007/978-3-642-32589-2_25 (DOI)2-s2.0-84864976736 (Scopus ID)0b993c78-df53-4868-92c0-a861554a87a6 (Local ID)9783642325885 (ISBN)0b993c78-df53-4868-92c0-a861554a87a6 (Archive number)0b993c78-df53-4868-92c0-a861554a87a6 (OAI)
##### Conference

International Symposium on Mathematical Foundations of Computer Science : 27/08/2012 - 31/08/2012
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt379",{id:"formSmash:j_idt204:0:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt385",{id:"formSmash:j_idt204:0:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt391",{id:"formSmash:j_idt204:0:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt391",multiple:true});
#####

##### Note

Validerad; 2012; 20120827 (andbra)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.

Faculty 3-Mathematics and Computer Science, University of Bremen.

Department of Computer Science, University of Copenhagen.

Department of Computer Science, University of Copenhagen.

We show how to build a binary heap in-place in linear time by performing ~ 1.625n element comparisons, at most ~ 2.125n element moves, and ~ n/B cache misses, where n is the size of the input array, B the capacity of the cache line, and ~ f(n) approaches f(n) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ(n) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size and adjust the heap order at the upper levels using Floyd's sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.

Open this publication in new window or tab >>Computing maximum-scoring segments optimally### Bengtsson, Fredrik

### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_some",{id:"formSmash:j_idt204:1:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_otherAuthors",{id:"formSmash:j_idt204:1:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_otherAuthors",multiple:true}); 2007 (English)Report (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Luleå: Luleå tekniska universitet, 2007. p. 10
##### Series

Research report / Luleå University of Technology, ISSN 1402-1528 ; 2007:3
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-22852 (URN)48a93dc0-5d75-11dc-8151-000ea68e967b (Local ID)48a93dc0-5d75-11dc-8151-000ea68e967b (Archive number)48a93dc0-5d75-11dc-8151-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt379",{id:"formSmash:j_idt204:1:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt385",{id:"formSmash:j_idt204:1:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt391",{id:"formSmash:j_idt204:1:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt391",multiple:true});
#####

##### Note

Godkänd; 2007; 20070907 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.

Given a sequence of length n, the problem studied in this report is to find a set of k disjoint subsequences of consecutive elements such that the total sum of all elements in the set is maximized. This problem arises in the analysis of DNA sequences. The previous best known algorithm requires time proportional to n times the inverse Ackermann function of (n,n), in the worst case. We present a linear-time algorithm, which is optimal, for this problem.

Open this publication in new window or tab >>Ranking k maximum sums### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_some",{id:"formSmash:j_idt204:2:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_otherAuthors",{id:"formSmash:j_idt204:2:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_otherAuthors",multiple:true}); 2007 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 377, no 1-3, p. 229-237Article in journal (Refereed) Published
##### Abstract [en]

##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-2927 (URN)10.1016/j.tcs.2007.03.011 (DOI)000247279200017 ()2-s2.0-34247634994 (Scopus ID)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (Local ID)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (Archive number)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt379",{id:"formSmash:j_idt204:2:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt385",{id:"formSmash:j_idt204:2:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt391",{id:"formSmash:j_idt204:2:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt391",multiple:true});
#####

##### Note

Validerad; 2007; 20070904 (pafi)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Given a sequence of n real numbers and an integer parameter k, the problem studied in this paper is to compute k subsequences of consecutive elements with the sums of their elements being the largest, the second largest, and the kth largest among all possible range sums of the input sequence. For any value of k, 1 <= k <= n (n + 1)/2, we design a fast algorithm that takes O (n + k log n) time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for k = O (n) by providing a matching lower bound.Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined).Furthermore, given the fact that we have computed the fth largest sums, our algorithm retrieves the (l + 1)th largest sum in O (log n) time, after O (n) time of preprocessing.

Open this publication in new window or tab >>Computing maximum-scoring segments in almost linear time### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_some",{id:"formSmash:j_idt204:3:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_otherAuthors",{id:"formSmash:j_idt204:3:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_otherAuthors",multiple:true}); 2006 (English)Report (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Luleå: Luleå tekniska universitet, 2006. p. 21
##### Series

Research report / Luleå University of Technology, ISSN 1402-1528 ; 2006:14
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-25447 (URN)f3c6bb30-b210-11db-bf9d-000ea68e967b (Local ID)f3c6bb30-b210-11db-bf9d-000ea68e967b (Archive number)f3c6bb30-b210-11db-bf9d-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt379",{id:"formSmash:j_idt204:3:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt385",{id:"formSmash:j_idt204:3:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt391",{id:"formSmash:j_idt204:3:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt391",multiple:true});
#####

##### Note

Godkänd; 2006; 20070201 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires n log n time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(n a(n, n) ) time in the worst case, where a(n,n) is the inverse Ackermann function.

Open this publication in new window or tab >>Computing maximum-scoring segments in almost linear time### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_some",{id:"formSmash:j_idt204:4:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_otherAuthors",{id:"formSmash:j_idt204:4:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_otherAuthors",multiple:true}); 2006 (English)In: Computing and Combinatorics: 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings / [ed] Danny Z. Chen, Encyclopedia of Global Archaeology/Springer Verlag, 2006, p. 255-264Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Encyclopedia of Global Archaeology/Springer Verlag, 2006
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 4112
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-31459 (URN)10.1007/11809678_28 (DOI)2-s2.0-33749543482 (Scopus ID)5a2a9d00-7bed-11dc-a72d-000ea68e967b (Local ID)978-3-540-36925-7 (ISBN)5a2a9d00-7bed-11dc-a72d-000ea68e967b (Archive number)5a2a9d00-7bed-11dc-a72d-000ea68e967b (OAI)
##### Conference

Annual International Computing and Combinatorics Conference : 15/08/2006 - 18/08/2006
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt379",{id:"formSmash:j_idt204:4:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt385",{id:"formSmash:j_idt204:4:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt391",{id:"formSmash:j_idt204:4:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt391",multiple:true});
#####

##### Note

Validerad; 2006; 20071016 (bson)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2020-08-26Bibliographically approved

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.

Open this publication in new window or tab >>Efficient algorithms for k maximum sums### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_some",{id:"formSmash:j_idt204:5:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_otherAuthors",{id:"formSmash:j_idt204:5:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_otherAuthors",multiple:true}); 2006 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, no 1, p. 27-41Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

Algorithm complexity, Algorithm design, Maximum subarray, Maximum subsequence, Maximum sum
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-15460 (URN)10.1007/s00453-006-0076-x (DOI)000240060500004 ()2-s2.0-33747888787 (Scopus ID)ef8af840-7bed-11dc-a72d-000ea68e967b (Local ID)ef8af840-7bed-11dc-a72d-000ea68e967b (Archive number)ef8af840-7bed-11dc-a72d-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt379",{id:"formSmash:j_idt204:5:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt385",{id:"formSmash:j_idt204:5:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt391",{id:"formSmash:j_idt204:5:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt391",multiple:true});
#####

##### Note

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers {x1,x2,...,xn} and an integer parameter k, 1 ≤ k ≤ 1/2n(n-1),the problem involves finding the k largest values of ∑ℓ=ijxℓ for 1 ≤ i ≤ j ≤ n.The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a Θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in O(min {k+nlog2n,n√k} ) time in the worst case. Our algorithm is optimal for k = Ω(n log 2 n) and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.

Validerad; 2006; 20071016 (bson)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2023-11-09Bibliographically approvedOpen this publication in new window or tab >>A note on ranking k maximum sums### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_some",{id:"formSmash:j_idt204:6:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_otherAuthors",{id:"formSmash:j_idt204:6:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_otherAuthors",multiple:true}); 2005 (English)Report (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Luleå: Luleå tekniska universitet, 2005. p. 9
##### Series

Research report / Luleå University of Technology, ISSN 1402-1528 ; 2005:08
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-23826 (URN)894036c0-b2a0-11db-bf9d-000ea68e967b (Local ID)894036c0-b2a0-11db-bf9d-000ea68e967b (Archive number)894036c0-b2a0-11db-bf9d-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt379",{id:"formSmash:j_idt204:6:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt385",{id:"formSmash:j_idt204:6:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt391",{id:"formSmash:j_idt204:6:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt391",multiple:true});
#####

##### Note

Godkänd; 2005; 20070202 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

In this paper, we design a fast algorithm for ranking the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem is to compute k subsequences of consecutive elements with the sums of their elements being the largest, second largest, ..., and the k:th largest among all possible range sums. For any value of k, 1 <= k <= n(n+1)/2, our algorithm takes O(n + k log n) time in the worst case to rank all such subsequences. Our algorithm is optimal for k <= n.

Open this publication in new window or tab >>Computing the k maximum subarrays fast### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_some",{id:"formSmash:j_idt204:7:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_otherAuthors",{id:"formSmash:j_idt204:7:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_otherAuthors",multiple:true}); 2004 (English)Report (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Luleå: Luleå tekniska universitet, 2004. p. 7
##### Series

Research report / Luleå University of Technology, ISSN 1402-1528 ; 2004:07
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-25205 (URN)e2ef04f0-ece6-11db-bc0c-000ea68e967b (Local ID)e2ef04f0-ece6-11db-bc0c-000ea68e967b (Archive number)e2ef04f0-ece6-11db-bc0c-000ea68e967b (OAI)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt379",{id:"formSmash:j_idt204:7:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt385",{id:"formSmash:j_idt204:7:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt391",{id:"formSmash:j_idt204:7:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt391",multiple:true});
#####

##### Note

Godkänd; 2004; 20070417 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

We study the problem of computing the k maximum sum subarrays. Given an array of real numbers and an integer, k, the problem involves finding the k largest values of the sum from i to j of the array, for any i and j. The problem for fixed k=1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. In this paper, we develop an algorithm requiring time proportional to n times square root of k for an array of length n. Moreover, for two-dimensional version of the problem, which computes the k largest sums over all rectangular subregions of an m times n array of real numbers, we show that it can be solved efficiently in the worst case as well.

Open this publication in new window or tab >>Efficient algorithms for k maximum sums### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_some",{id:"formSmash:j_idt204:8:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_otherAuthors",{id:"formSmash:j_idt204:8:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_otherAuthors",multiple:true}); 2004 (English)In: Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings / [ed] Rudolf Fleischer; Gerhard Trippen, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2004, p. 137-148Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2004
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 3341
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-35524 (URN)10.1007/978-3-540-30551-4_14 (DOI)2-s2.0-26844581198 (Scopus ID)a13f3f40-7beb-11dc-a72d-000ea68e967b (Local ID)978-3-540-24131-7 (ISBN)978-3-540-30551-4 (ISBN)a13f3f40-7beb-11dc-a72d-000ea68e967b (Archive number)a13f3f40-7beb-11dc-a72d-000ea68e967b (OAI)
##### Conference

International Symposium on Algorithms and Computation : 20/12/2004 - 22/12/2004
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt379",{id:"formSmash:j_idt204:8:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt385",{id:"formSmash:j_idt204:8:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt391",{id:"formSmash:j_idt204:8:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt391",multiple:true});
#####

##### Note

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers (x1,x2,⋯,xn) and an integer parameter k, l ≤ k ≤ 1/2n(n -1), the problem involves finding the k largest values of Σl=ij xl for 1 ≤ i ≤ j ≤ n. The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper, we design efficient algorithms that solve the above problem in O (min{k + n log2 n, n √k}) time in the worst case. Our algorithm is optimal for k ≥ n log2 n and improves over the previously best known result for any value of the user-defined parameter k. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.

Validerad; 2004; 20071016 (bson)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2023-11-09Bibliographically approvedOpen this publication in new window or tab >>Space-efficient range-sum queries in OLAP### Bengtsson, Fredrik

Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.### Chen, Jingsen

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_some",{id:"formSmash:j_idt204:9:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_otherAuthors",{id:"formSmash:j_idt204:9:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_otherAuthors",multiple:true}); 2004 (English)In: Data Warehousing and Knowledge Discovery. Proceedings: 6th international conference, DaWaK 2004, Zaragoza, Spain, September 1 - 3, 2004 : proceedings / [ed] Yahiko Kambayashi; Mukesh Mohania; Wolfram Wöß, Encyclopedia of Global Archaeology/Springer Verlag, 2004, p. 87-96Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Encyclopedia of Global Archaeology/Springer Verlag, 2004
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 3181
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

urn:nbn:se:ltu:diva-34204 (URN)10.1007/978-3-540-30076-2_9 (DOI)2-s2.0-33845655201 (Scopus ID)8563f470-c1ea-11db-9ea3-000ea68e967b (Local ID)978-3-540-22937-7 (ISBN)978-3-540-30076-2 (ISBN)8563f470-c1ea-11db-9ea3-000ea68e967b (Archive number)8563f470-c1ea-11db-9ea3-000ea68e967b (OAI)
##### Conference

International Conference on Data Warehousing and Knowledge Discovery : 01/09/2004 - 03/09/2004
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt379",{id:"formSmash:j_idt204:9:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt385",{id:"formSmash:j_idt204:9:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt391",{id:"formSmash:j_idt204:9:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt391",multiple:true});
#####

##### Note

In this paper, we present a fast algorithm to answer range-sum queries in OLAP data cubes. Our algorithm supports constant-time queries while maintaining sub-linear time update and using minimum space. Furthermore, we study the trade-off between query time and update time. The complexity for query is O(2ℓd) and for updates O((2ℓ2ℓ√n)d) on a data cube of nd elements, where ℓ is a trade-off parameter. Our algorithm improve over previous best known results

Validerad; 2004; 20070105 (pafi)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2020-08-26Bibliographically approved