Аноним

Задача об упаковке в контейнеры: различия между версиями

Материал из WEGA
Строка 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 позволяет устранить случай ©(log n) условия 2.
'''Кроме того, простая модификация SS позволяет исключить случай <math>\Theta(log \; n) \}</math> в условии 2.


== Применение ==
== Применение ==
4551

правка