Минимальная продолжительность потока: различия между версиями

Онлайновый алгоритм Леонарди и Раза также является самым известным оффлайновым аппроксимационным алгоритмом для этой задачи. В частности, неизвестно, существует ли аппроксимация с коэффициентом O(1) даже для случая двух машин. Решить этот вопрос было бы очень интересно. В смежной работе Бансал [3] рассмотрел задачу расчета немигрирующих расписаний для постоянного числа машин. Он предложил алгоритм, который выдает решение с коэффициентом аппроксимации <math>1 + \epsilon</math> для любого <math>\epsilon > 0</math> за время <math>n^{O(log \; n / \epsilon^2)}</math>. Это говорит о возможности создания для этой задачи схемы аппроксимации с полиномиальным временем выполнения – по крайней мере, для случая постоянного числа машин.