Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints

Sung Kwon KIM  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.2   pp.250-256
Publication Date: 2010/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.250
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
length constraint,  longest subsequence,  offline algorithm,  online algorithm,  shortest subsequence,  sum constraint,  

Full Text: PDF(553KB)>>
Buy this Article




Summary: 
In this paper, we address the following problems: Given a sequence A of n real numbers, and four parameters I,J,X and Y with IJ and XY, find the longest (or shortest) subsequence of A such that its length is between I and J and its sum is between X and Y. We present an online and an offline algorithm for the problems, both run in O(nlog n) time, which are optimal.