1632
правки
Изменения
м
rollbackEdits.php mass rollback
</ol>
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..\ldots n} (C_i - d_i)</tex> было минимальным.}}
== Решение ==
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - . Cеть]]
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
Т.к. сеть содержит <tex>O(n)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(n^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(n^3)</tex> операций.
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(\log(n) + \log(\cfrac{1}{\varepsilon}) + \log(\max\limits_{j=1..\ldots n} (p_j))) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n\max\limits_{j=1..\ldots n} (p_j)</tex>
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
