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...
Gorde:
| Egile Nagusiak: | , , , |
|---|---|
| Formatua: | Artikulua |
| Argitaratua: |
2020
|
| Gaiak: | |
| Sarrera elektronikoa: | https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498 |
| Etiketak: |
Etiketarik gabe, Izan zaitez lehena erregistro honi etiketa jartzen!
|