Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Táto stránka sa týka školského roku 2016/17. V školskom roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://people.ksp.sk/~kuko/ds


Vyhľadávanie vzorky v texte

Z VPDS
Prejsť na: navigácia, hľadanie

Theoretical results for edit distance computation

Exact algorithm O(mn) or improved by logarithimc factor.

Approximation algorithm: For strings of length n and every fixed ε > 0 compute (\log n)^{{O(1/\epsilon )}} approximation in n^{{1+\epsilon }} time

Source: Andoni A, Krauthgamer R, Onak K. Polylogarithmic approximation for edit distance and the asymmetric query complexity. FOCS2010, pp. 377-386 [1]

Conditional lower bound: If the edit distance can be computed in O(n^{{2-\delta }}) for some constant δ > 0, then the satisfiability of conjunctive normal form (CNF) formulas with N variables and M clauses can be solved in time M^{{O(1)}}2^{{(1-\epsilon )N}} for a constant \epsilon >0, which would violate Strong Exponential Time Hypothesis (SETH).

Source: Backurs A, Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC2015, pp. 51-58 [2]


Literatúra