4446
правок
Нахождение ближайшей подстроки: различия между версиями
Материал из WEGA
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 13:42, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 27: | Строка 27: | ||
Следующая теорема дает ключевое представление об аппроксимируемости задачи: | Следующая теорема дает ключевое представление об аппроксимируемости задачи: | ||
'''Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение схем | '''Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение аппроксимационных схем с полиномиальным временем выполнения (PTAS), в которых целевой функцией является минимальное расстояние Хэмминга d.''' | ||
| Строка 67: | Строка 67: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается нерешенным вопрос [7], можно ли схему | Остается нерешенным вопрос [7], можно ли аппроксимационную схему с временем выполнения <math>n^{O(1 / \epsilon^4)}</math>, предложенную в работе [6], улучшить до <math>n^{O(log \; 1 / \epsilon)}</math> в соответствии с границей, полученной на основе теоремы 4. | ||
== См. также == | == См. также == | ||
