1313
правок
Задача о кратчайшем векторе: различия между версиями
Материал из WEGA
Задача о кратчайшем векторе (посмотреть исходный код)
Версия от 04:49, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 39: | Строка 39: | ||
Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм | Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) аппроксимационный алгоритм с полиномиальным временем выполнения достигает коэффициента аппроксимации <math>\gamma = 2^{O(n \; log \; log \; n / log \; n)}</math>. | ||
== Применение == | == Применение == | ||
| Строка 119: | Строка 119: | ||
15. Vazirani, V.V.: Approximation Algorithms. Springer (2001) | 15. Vazirani, V.V.: Approximation Algorithms. Springer (2001) | ||
[[Категория: Совместное определение связанных терминов]] | |||
