de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Encodings of Range Maximum-Sum Segment Queries and Applications

Gawrychowski, P., & Nicholson, P. K. (2014). Encodings of Range Maximum-Sum Segment Queries and Applications. Retrieved from http://arxiv.org/abs/1410.2847.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0024-4465-5 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-0024-AA73-E
Genre: Paper

Files

show Files
hide Files
:
arXiv:1410.2847.pdf (Preprint), 488KB
Description:
File downloaded from arXiv at 2014-12-01 10:14
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Gawrychowski, Paweł1, Author              
Nicholson, Patrick K.1, Author              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: Given an array A containing arbitrary (positive and negative) numbers, we consider the problem of supporting range maximum-sum segment queries on A: i.e., given an arbitrary range [i,j], return the subrange [i' ,j' ] \subseteq [i,j] such that the sum of the numbers in A[i'..j'] is maximized. Chen and Chao [Disc. App. Math. 2007] presented a data structure for this problem that occupies {\Theta}(n) words, can be constructed in {\Theta}(n) time, and supports queries in {\Theta}(1) time. Our first result is that if only the indices [i',j'] are desired (rather than the maximum sum achieved in that subrange), then it is possible to reduce the space to {\Theta}(n) bits, regardless the numbers stored in A, while retaining the same construction and query time. We also improve the best known space lower bound for any data structure that supports range maximum-sum segment queries from n bits to 1.89113n - {\Theta}(lg n) bits, for sufficiently large values of n. Finally, we provide a new application of this data structure which simplifies a previously known linear time algorithm for finding k-covers: i.e., given an array A of n numbers and a number k, find k disjoint subranges [i_1 ,j_1 ],...,[i_k ,j_k ], such that the total sum of all the numbers in the subranges is maximized.

Details

show
hide
Language(s): eng - English
 Dates: 2014-10-102014-11-242014-11-24
 Publication Status: Published online
 Pages: 20 pages + 2 page appendix, 4 figures. This version: corrected a few typos and metadata
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: arXiv: 1410.2847
URI: http://arxiv.org/abs/1410.2847
BibTex Citekey: DBLP:journals/corr/NicholsonG14
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show