Списочное планирование: различия между версиями

Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [9] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную <math>\frac{4}{3} - \frac{1}{3m}</math>. Схему аппроксимации с полиномиальным временем выполнения предложили Хохбаум и Шмойс в работе [10]. Это лучший оффлайновый результат, на который можно было бы надеяться, поскольку, как известно, задача является NP-трудной в сильном смысле.

В процессе последующего изучения алгоритмов аппроксимации (и в особенности онлайновых алгоритмов) при анализе многих алгоритмов планирования использовались методы, аналогичные приведенному выше доказательству. Далее приведены несколько вариантов задачи, в которых практически то же доказательство дает в результате точно такую же границу.