Просмотр исходного текста страницы Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling

<!-- cabook-th-02-07-p71 -->

Рассмотрим задачу [[Планирование Задач на Одинаковых Машинах]]
и применим к ней LPT<ref>Largest Processing Time</ref>-эвристику:
* отсортировать задачи по убыванию длины
* для каждой задачи:
** применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину

Докажите, что в, 

<m>
 \frac{M_{LPT}}{OPT(x)} < \frac{1}{3} ( 4  — \frac1p )
</m>

* OPT(x) — значение этого оптимального решения.
* <m>M_{LPT}</m> — значение, найденное алгоритмом

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]