251
правка
Изменения
→Время работы
Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q \mid pmtn; r_{i} \mid L_{max}</tex> мы используем бинарный поиск, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (mn^3(\log(n) + \log(1 / \varepsilon) + \log(\max\limits_{i=1}^{n} p_i)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
Задача <tex>Q \mid pmtn; r_i \mid C_{max}</tex> представляет собой частный случай <tex>Q \mid pmtn; r_i \mid L_{max}</tex>, и может быть решена более эффективно<ref>Описано в Peter Brucker. Лабетоль (Labetoulle J.)«Scheduling Algorithms» {{---}} «Springer», Лаулер (Lawler E2006 г.L{{---}} 133 стр.), Ленстра (Lenstra. J.K.), и Ринной Кан (Rinnooy Kan A.H.G.) разработали алгоритм работающий за <tex> O(n \log(n) + mn) </texref> специально для этого случая.
==Источники информации==
