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 of 𝑓’s LIS within ±𝜖𝑛 using 𝑂(𝑟𝜖⁻²) · 𝑝𝑜𝑙𝑦(log 𝜖 ⁻¹) samples and 𝑂(𝑟𝜖⁻²) · 𝑝𝑜𝑙𝑦(log 𝑟, log 𝜖 ⁻¹) runtime. Our approache introduces small adjustments to the previously known algorithm for this problem, due to [5], resulting in a polynomial runtime algorithm which uses less queries by a factor of 𝜖 ⁻¹. Similar approaches can also be applied to estimating edit distance to monotonicity in 2-dimenstional array and 𝐿₁ edit distance of a sequence within sublinear time using 𝑝𝑜𝑙𝑦(𝑟, 𝜖⁻¹) queries.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Sawettamalya, Pachara

Advisor dc:contributor.advisor

• Rubinfeld, Ronitt

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/144937

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/144937