LOWER BOUNDS ON STREAMING ALGORITHMS FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceed...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2010-01, Vol.39 (7-8), p.3463-3479
Main Authors: GAL, Anna, GOPALAN, Parikshit
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Asymptotic properties
Codes
Computation
Computer science
control theory
systems
Exact sciences and technology
Lower bounds
Mathematical analysis
Miscellaneous
Studies
Symbols
Theoretical computing
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space ... This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.(ProQuest: ... denotes formulae/symbols omitted.) [PUBLICATION ABSTRACT]
ISSN:0097-5397
1095-7111
DOI:10.1137/090770801