Space Efficient Deterministic Approximation of String Measures

We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with ro...

Fuld beskrivelse

Bibliografiske detaljer

Autores principales:	Cheng, Kuan, Jin, Zhengzhong, Li, Xin, Zheng, Yu
Format:	Artículo
Udgivet:	2020
Fag:	Data Structures and Algorithms
Online adgang:	https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498
Tags:	Tilføj Tag Ingen Tags, Vær først til at tagge denne postø!