Изменения

Перейти к: навигация, поиск

Tango-дерево

Нет изменений в размере, 20:45, 11 июня 2014
м
Вторая нижняя оценка Уилбера (Wilber)
{{Определение
|definition=Числом Уилбера <tex>ch(ij)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
}}
Получаем следующую оценку
<tex>OPT \geqslant \sum\limits_{i j \in [1, n]} 1 + ch(ij)</tex>Это можно вывести из предыдущей оценки, построив соответствующее <tex>ch(ij)</tex> множество попарно независимых прямоугольников.
[[Файл:DariaPicture11.png|300px]]
170
правок

Навигация