4551
правка
Задача о кратчайшем векторе: различия между версиями
Материал из WEGA
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 13:22, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 39: | Строка 39: | ||
Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм | Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) аппроксимационный алгоритм с полиномиальным временем выполнения достигает коэффициента аппроксимации <math>\gamma = 2^{O(n \; log \; log \; n / log \; n)}</math>. | ||
== Применение == | == Применение == | ||
