Задача об упаковке в контейнеры: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 146: | Строка 146: | ||
'''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения | '''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения:''' | ||
'''1. Если <math>EW^n_{OPT}(F) = \Theta(\sqrt{n})</math>, то <math>EW^n_{SS}(F) = \Theta(\sqrt{n}).</math>''' | |||
'''2. Если <math>EW^n_{OPT}(F) = O(1)</math>, то <math>EW^n_{SS}(F) \in \{ O(1), \Theta(log \; n) \}.</math>''' | |||
Кроме того, простая модификация SS позволяет | '''Кроме того, простая модификация SS позволяет исключить случай <math>\Theta(log \; n) \}</math> в условии 2. | ||
== Применение == | == Применение == | ||