Name
Abstract | ||
|---|---|---|
In this paper we consider problems related to the sortedness of a data stream. First we investigate the problem of estimating the distance to monotonicity; given a sequence of length n, we give a deterministic (2 + ε)-approximation algorithm for estimating its distance to monotonicity in space O(1/ε2 log2 (εn)). This improves over the randomized (4 + ε)-approximation, algorithm of [3]. We then consider the problem of approximating the length of the longest increasing subsequence of an input stream of length n. We use techniques from multi-party communication complexity combined with a fooling set approach to prove that any O(1)-pass deterministic streaming algorithm that approximates the length of the longest increasing subsequence within 1 + ε requires Ω(√n) space. This proves the conjecture in [3] and matches the current upper bound. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.5555/1347082.1347162 | SODA |
Keywords | Field | DocType |
input stream,fooling set approach,length n,multi-party communication complexity,approximation algorithm,data stream,space o,upper bound,longest increasing subsequence,streaming algorithm,communication complexity | Monotonic function,Discrete mathematics,Combinatorics,Longest common subsequence problem,Longest increasing subsequence,Streaming algorithm,Upper and lower bounds,Data stream,Communication complexity,Conjecture,Mathematics | Conference |
ISBN | Citations | PageRank |
978-0-89871-698-6 | 16 | 0.79 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Funda Ergun | 1 | 151 | 10.13 |
| Hossein Jowhari | 2 | 172 | 8.53 |