Home
Resource
Very efficient approximation algorithms to edit distance problems
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(789.47 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Naumovitz, Timothy Ryan. Very efficient approximation algorithms to edit distance problems. Retrieved from https://doi.org/doi:10.7282/T3J38VXK

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleVery efficient approximation algorithms to edit distance problems
NameNaumovitz, Timothy Ryan (author); Saks, Michael (chair); Saraf, Shubhangi (internal member); Szegedy, Mario (internal member); Andoni, Alexandr (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2016
Other Date2016-10 (degree)
SubjectMathematics, Computer algorithms, Approximation theory
Extent1 online resource (vii, 104 p. : ill.)
DescriptionThis thesis deals with the question of approximating distance to monotonicity in the streaming setting as well as the task of approximating the ulam distance between two permutations. Both of these problems are variants of the edit distance problem which, given two input sequences, is the minimum number of insertions and deletions (and in some cases, substitutions) needed to transform one sequence into the other. The distance to monotonicity of a sequence of n numbers is the minimum number of entries whose deletion leaves an increasing sequence. We give the first deterministic streaming algorithm that approximates the distance to monotonicity within a 1+ ε factor for any fixed ε > 0 and runs in space polylogarithmic in the length of the sequence and the range of the numbers. The best previous deterministic algorithm achieving the same approximation factor required space Ω(√ n) [13]. Previous polylogarithmic space algorithms were either randomized [22], or had approximation factor no better than 2 [9]. We also give polylogarithmic space lower bounds for this problem: Any deterministic streaming algorithm that gets a 1 + ε approximation requires space Ω( 1 ε log2 (n)) and any randomized algorithm requires space Ω( 1 ε log2 (n) log log(n) ). 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. We provide an algorithm which, for any fixed ε > 0, gives a (1 + ε)-multiplicative approximation for the Ulam distance d in O˜ ε(n/d + √ 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 [4] with the same running time bound (ignoring polylogarithmic factors).
NotePh.D.
NoteIncludes bibliographical references
Noteby Timothy Ryan Naumovitz
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3J38VXK
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024