Single and dual wavelength exposure of photoresist
J. LaRue, C. Ting
Proceedings of SPIE 1989
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet ∑ has length at least k, we discuss a one-pass algorithm using O(k og |∑|) space, with update time either O(log k:) or O(log log |σ|); for |σ| = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of ω(k) on the space requirement for this problem for general alphabets E, even when the input stream is a permutation of ∑. For finding the actual LIS, we give a [log(1 + 1/epsi;)]-pass algorithm using O(k 1+ε log |∑|) space, for any ε > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when |∑| = O(1). For general alphabets ∑, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Ω(n/ρ 2) space to approximate the LCS of two n-element streams to within a factor of p, even if the streams are permutations of each other. © Springer Science + Business Media, LLC 2006.
J. LaRue, C. Ting
Proceedings of SPIE 1989
Chai Wah Wu
Linear Algebra and Its Applications
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences