170
правок
Изменения
→Вторая нижняя оценка Уилберра (Wilber)
В каждый момент времени позиция <tex>a_{i}</tex> может увеличиваться, <tex>b_{i}</tex> уменьшаться.
Напишем <tex>r</tex>, если изменяется правая граница <tex>b_{i]}</tex> и <tex>l</tex> - если левая.
Числом Уилберра <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
<tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
[[Файл:DariaPicture10DariaPicture11.png|200px300px]]
{{Теорема
