Fast Algorithms for Bounded-Range LIS Approximation
We introduce an improvement to additive approximation of Longest Increasing Subsequence (LIS) of a sequence with a bounded number of unique elements. In particular, for a sequence 𝑓 of length 𝑛 with 𝑟 unique elements and 𝜖 additive error paramenter, we present an algorithm that approximate the size...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144937 |