Accurate and nearly optimal sublinear approximations to ulam distance

Timothy Naumovitz, Michael Saks, C. Seshadhri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

The Ulam distance between two permutations of length n is the minimum number of insertions and deletions needed to transform one sequence into the other. Equivalently, the Ulam distance d is n minus the length of the longest common subsequence (LCS) between the permutations. Our main result is an algorithm, that for any fixed " > 0, provides a (1 + ∈)-multiplicative approximation for d in O(n=d + p n) time, which has been shown to be optimal up to polylogarithmic factors. This is the first sublinear time algorithm (provided that d = (log n)!(1)) that obtains arbitrarily good multiplicative approximations to the Ulam distance. The previous best bound is an O(1)-approximation (with a large constant) by Andoni and Nguyen (2010) with the same running time bound (ignoring polylogarithmic factors). The improvement in the approximation factor from O(1) to (1+∈) allows for significantly more powerful sublinear algorithms. For example, for any fixed δ > 0, we can get additive δn approximations for the LCS between permutations in O( p √n) time. Previous sublinear algorithms require δ to be at least 11=C, where C is the approximation factor, which is close to 1 when C is large. Our algorithm is obtained by abstracting the basic algorithmic framework of Andoni and Nguyen, and combining it with the sublinear approximations for the longest increasing subsequence by Saks and Seshadhri (2010).

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages2012-2031
Number of pages20
ISBN (Electronic)9781611974782
DOIs
StatePublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Country/TerritorySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Accurate and nearly optimal sublinear approximations to ulam distance'. Together they form a unique fingerprint.

Cite this